哈希表的C++实现，可以直接编译使用

/********** This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version. (See <http://www.gnu.org/copyleft/lesser.html>.) This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public License along with this library; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA **********/ // Copyright (c) 1996-2024 Live Networks, Inc. All rights reserved. // Basic Hash Table implementation // Implementation #include "BasicHashTable.hh" #include "strDup.hh" #if defined(__WIN32__) || defined(_WIN32) #else #include <stddef.h> #endif #include <string.h> // When there are this many entries per bucket, on average, rebuild // the table to increase the number of buckets #define REBUILD_MULTIPLIER 3 BasicHashTable::BasicHashTable(int keyType) : fBuckets(fStaticBuckets), fNumBuckets(SMALL_HASH_TABLE_SIZE), fNumEntries(0), fRebuildSize(SMALL_HASH_TABLE_SIZE*REBUILD_MULTIPLIER), fDownShift(28), fMask(0x3), fKeyType(keyType) { for (unsigned i = 0; i < SMALL_HASH_TABLE_SIZE; ++i) { fStaticBuckets[i] = NULL; } } BasicHashTable::~BasicHashTable() { // Free all the entries in the table: for (unsigned i = 0; i < fNumBuckets; ++i) { TableEntry* entry; while ((entry = fBuckets[i]) != NULL) { deleteEntry(i, entry); } } // Also free the bucket array, if it was dynamically allocated: if (fBuckets != fStaticBuckets) delete[] fBuckets; } // 添加一个键值对到哈希表，2024-07-22 23:49:05 void* BasicHashTable::Add(char const* key, void* value) { void* oldValue; unsigned index; TableEntry* entry = lookupKey(key, index); if (entry != NULL) { // There's already an item with this key oldValue = entry->value; } else { // There's no existing entry; create a new one: entry = insertNewEntry(index, key); oldValue = NULL; } entry->value = value; // If the table has become too large, rebuild it with more buckets: if (fNumEntries >= fRebuildSize) rebuild(); return oldValue; } // 删除一个键值对(entry)，2024-07-22 23:49:08 Boolean BasicHashTable::Remove(char const* key) { unsigned index; TableEntry* entry = lookupKey(key, index); if (entry == NULL) return False; // no such entry deleteEntry(index, entry); return True; } // 查找，根据key找到value，2024-07-22 23:48:20 void* BasicHashTable::Lookup(char const* key) const { unsigned index; TableEntry* entry = lookupKey(key, index); if (entry == NULL) return NULL; // no such entry return entry->value; } // 哈希表总的键值对(entry)个数，2024-07-22 23:47:35 unsigned BasicHashTable::numEntries() const { return fNumEntries; } // 迭代器，用于迭代传入的哈希表 2024-07-22 23:43:05 BasicHashTable::Iterator::Iterator(BasicHashTable const& table) : fTable(table), fNextIndex(0), fNextEntry(NULL) { } // 返回下一个键值对(entry)的关键字(key)和值(value),2024-07-22 23:46:50 void* BasicHashTable::Iterator::next(char const*& key) { while (fNextEntry == NULL) { if (fNextIndex >= fTable.fNumBuckets) return NULL; fNextEntry = fTable.fBuckets[fNextIndex++]; } BasicHashTable::TableEntry* entry = fNextEntry; fNextEntry = entry->fNext; key = entry->key; return entry->value; } ////////// Implementation of HashTable creation functions ////////// HashTable* HashTable::create(int keyType) { return new BasicHashTable(keyType);// 父类指针指向子类对象 2024-07-22 23:44:39 } HashTable::Iterator* HashTable::Iterator::create(HashTable const& hashTable) { // "hashTable" is assumed to be a BasicHashTable return new BasicHashTable::Iterator((BasicHashTable const&)hashTable);// 父类指针指向子类对象 2024-07-22 23:44:39 } ////////// Implementation of internal member functions ////////// // 根据key找到一个键值对(entry),下标index，2024-07-22 23:36:55 BasicHashTable::TableEntry* BasicHashTable ::lookupKey(char const* key, unsigned& index) const { TableEntry* entry; index = hashIndexFromKey(key); for (entry = fBuckets[index]; entry != NULL; entry = entry->fNext) { if (keyMatches(key, entry->key)) break; } return entry; } // 比较两个key是否一致 2024-07-22 23:35:24 Boolean BasicHashTable ::keyMatches(char const* key1, char const* key2) const { // The way we check the keys for a match depends upon their type: if (fKeyType == STRING_HASH_KEYS) { return (strcmp(key1, key2) == 0); } else if (fKeyType == ONE_WORD_HASH_KEYS) { return (key1 == key2); } else { unsigned* k1 = (unsigned*)key1; unsigned* k2 = (unsigned*)key2; for (int i = 0; i < fKeyType; ++i) { if (k1[i] != k2[i]) return False; // keys differ } return True; } } // 生成一个entry, 插入到链表，并给entry->key赋值，2024-07-22 23:34:42 BasicHashTable::TableEntry* BasicHashTable ::insertNewEntry(unsigned index, char const* key) { TableEntry* entry = new TableEntry(); entry->fNext = fBuckets[index]; fBuckets[index] = entry; ++fNumEntries; assignKey(entry, key); return entry; } // 根据键值类型、key值，创建一个 Key，并赋值到entry的key字段 2024-07-22 21:16:20 void BasicHashTable::assignKey(TableEntry* entry, char const* key) { // The way we assign the key depends upon its type: if (fKeyType == STRING_HASH_KEYS) { entry->key = strDup(key); } else if (fKeyType == ONE_WORD_HASH_KEYS) { entry->key = key; } else if (fKeyType > 0) { unsigned* keyFrom = (unsigned*)key; unsigned* keyTo = new unsigned[fKeyType]; for (int i = 0; i < fKeyType; ++i) keyTo[i] = keyFrom[i]; entry->key = (char const*)keyTo; } } // 删除指定下标的一个键值对(Entry)，2024-07-22 21:20:18 void BasicHashTable::deleteEntry(unsigned index, TableEntry* entry) { TableEntry** ep = &fBuckets[index]; // 找到存在数组的位置 Boolean foundIt = False; while (*ep != NULL) { // 遍历链表 if (*ep == entry) { foundIt = True; *ep = entry->fNext; break; } ep = &((*ep)->fNext); } if (!foundIt) { // shouldn't happen #ifdef DEBUG fprintf(stderr, "BasicHashTable[%p]::deleteEntry(%d,%p): internal error - not found (first entry %p", this, index, entry, fBuckets[index]); if (fBuckets[index] != NULL) fprintf(stderr, ", next entry %p", fBuckets[index]->fNext); fprintf(stderr, ")\n"); #endif } --fNumEntries; deleteKey(entry); delete entry; } // 删除一个键值对(Entry)的Key，2024-07-22 21:21:12 void BasicHashTable::deleteKey(TableEntry* entry) { // The way we delete the key depends upon its type: if (fKeyType == ONE_WORD_HASH_KEYS) { entry->key = NULL; } else { delete[] (char*)entry->key; entry->key = NULL; } } // 重新建立一个哈希表，2024-07-22 21:22:08 void BasicHashTable::rebuild() { // Remember the existing table size: unsigned oldSize = fNumBuckets; TableEntry** oldBuckets = fBuckets; // Create the new sized table: fNumBuckets *= 4; fBuckets = new TableEntry*[fNumBuckets]; for (unsigned i = 0; i < fNumBuckets; ++i) { fBuckets[i] = NULL; } fRebuildSize *= 4; fDownShift -= 2; fMask = (fMask<<2)|0x3; // Rehash the existing entries into the new table: for (TableEntry** oldChainPtr = oldBuckets; oldSize > 0; --oldSize, ++oldChainPtr) { for (TableEntry* hPtr = *oldChainPtr; hPtr != NULL; hPtr = *oldChainPtr) { *oldChainPtr = hPtr->fNext; unsigned index = hashIndexFromKey(hPtr->key);