1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 | // RS Hash Function unsigned int RSHash (char *str) { unsigned int b = 378551; unsigned int a = 63689; unsigned int hash = 0; while (*str) { hash = hash * a + (*str++); a *= b; } return (hash & 0x7FFFFFFF); } // JS Hash Function unsigned int JSHash (char *str) { unsigned int hash = 1315423911; while (*str) { hash ^= ((hash << 5) + (*str++) + (hash >> 2)); } return (hash & 0x7FFFFFFF); } // P. J. Weinberger Hash Function unsigned int PJWHash (char *str) { unsigned int BitsInUnignedInt = (unsigned int) (sizeof (unsigned int) * 8); unsigned int ThreeQuarters = (unsigned int) ((BitsInUnignedInt * 3) / 4); unsigned int OneEighth = (unsigned int) (BitsInUnignedInt / 8); unsigned int HighBits = (unsigned int) (0xFFFFFFFF) << (BitsInUnignedInt - OneEighth); unsigned int hash = 0; unsigned int test = 0; while (*str) { hash = (hash << OneEighth) + (*str++); if ((test = hash & HighBits) != 0) { hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits)); } } return (hash & 0x7FFFFFFF); } // ELF Hash Function unsigned int ELFHash (char *str) { unsigned int hash = 0; unsigned int x = 0; while (*str) { hash = (hash << 4) + (*str++); if ((x = hash & 0xF0000000L) != 0) { hash ^= (x >> 24); hash &= ~x; } } return (hash & 0x7FFFFFFF); } // BKDR Hash Function unsigned int BKDRHash (char *str) { unsigned int seed = 131; // 31 131 1313 13131 131313 etc.. unsigned int hash = 0; while (*str) { hash = hash * seed + (*str++); } return (hash & 0x7FFFFFFF); } // SDBM Hash Function unsigned int SDBMHash (char *str) { unsigned int hash = 0; while (*str) { hash = (*str++) + (hash << 6) + (hash << 16) - hash; } return (hash & 0x7FFFFFFF); } // DJB Hash Function unsigned int DJBHash (char *str) { unsigned int hash = 5381; while (*str) { hash += (hash << 5) + (*str++); } return (hash & 0x7FFFFFFF); } // AP Hash Function unsigned int APHash (char *str) { unsigned int hash = 0; int i; for (i = 0; *str; i++) { if ((i & 1) == 0) { hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3)); } else { hash ^= (~((hash << 11) ^ (*str++) ^ (hash >> 5))); } } return (hash & 0x7FFFFFFF); } |
对最简单的SDBMHash(char*)做了一个简单的测试。随机生成200个长度为31的字符串，利用SDBM得到一个Hash值，然后用直接取余法插入长度为113的HashSet，为简单起见，只是将HashSet对应的位置进行加一。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | const int N = 32; char str[N]; int HashSet[113] = {0}; void RandStr(char* str, const int n) { int i = 0; for( ; i < n - 1; ++i) { str[i] = 'a' + rand() % 26; } str[i] = '\0'; } int main() { srand(time(NULL)); const int count = 200; for(int i = 0; i < count; ++i) { RandStr(str, N); HashSet[SDBMHash(str)%113]++; } FILE* out = fopen("./result.txt", "w"); //~ FILE* out = stdout; for(int i = 0; i < 113; ++i) { fprintf(out, "%d\n", HashSet[i]); } return 0; } |
测试效果还是很不错的，相当均匀了已经。
HashTest Diagram
No Comments Now!
Be the first to comment on this entry.