😁博客主页😁:🚀https://blog.csdn.net/wkd_007🚀
🤑博客内容🤑:🍭嵌入式开发、Linux、C语言、C++、数据结构、音视频🍭
🤣本文内容🤣:🍭介绍哈希表的实现 🍭
😎金句分享😎:🍭你不能选择最好的,但最好的会来选择你——泰戈尔🍭
⏰发布时间⏰: 2024-07-24 23:44:05
本文未经允许,不得转发!!!
目录
🎄一、概述
本文介绍Live555源码的哈希表实现,如果对哈希表不了解的,可以看这篇文章:https://blog.csdn.net/wkd_007/article/details/140655297
哈希表是存储 键值对 的一个数据结构。一个哈希表应该要提供插入元素、删除元素、查询元素的操作,而具体的哈希表实现还会出现哈希函数、处理哈希冲突、键值对相关结构体、比对键值等,我们看哈希表代码时需要格外注意这些实现。
下图是Live555哈希表相关类的关系图:
1、HashTable 是个基类,规范哈希表的接口;
2、BasicHashTable 是哈希表的具体实现;
3、TableEntry 是存储键值对的,同时它还有个指针指向自己,说明这里应该是使用 链地址法 来处理哈希冲突的。
Live555哈希表相关代码主要在这4个文件:HashTable.hh、HashTable.cpp、BasicHashTable.hh、BasicHashTable.cpp。主要涉及两个类,下面介绍具体实现。
🎄二、HashTable 类
HashTable 类声明:
class HashTable { public: virtual ~HashTable(); // The following must be implemented by a particular // implementation (subclass): static HashTable* create(int keyType); virtual void* Add(char const* key, void* value) = 0; // Returns the old value if different, otherwise 0 virtual Boolean Remove(char const* key) = 0; virtual void* Lookup(char const* key) const = 0; virtual unsigned numEntries() const = 0; // Returns 0 if not found Boolean IsEmpty() const { return numEntries() == 0; } // Used to iterate through the members of the table: class Iterator { public: // The following must be implemented by a particular // implementation (subclass): static Iterator* create(HashTable const& hashTable); virtual ~Iterator(); virtual void* next(char const*& key) = 0; // returns 0 if none protected: Iterator(); // abstract base class }; // A shortcut that can be used to successively remove each of // the entries in the table (e.g., so that their values can be // deleted, if they happen to be pointers to allocated memory). void* RemoveNext(); // Returns the first entry in the table. // (This is useful for deleting each entry in the table, if the entry's destructor also removes itself from the table.) void* getFirst(); protected: HashTable(); // abstract base class };
首先,我们看到 HashTable 类声明了4个纯虚函数:
virtual void* Add(char const* key, void* value) = 0;// Returns the old value if different, otherwise 0 virtual Boolean Remove(char const* key) = 0; virtual void* Lookup(char const* key) const = 0; virtual unsigned numEntries() const = 0;
这说明 HashTable 类是个抽象基类,所以它不会实例化对象,同时很可能会使用 HashTable 类的指针或引用去管理其派生类对象。这四个函数对应了哈希表的插入、删除、查询、哈希值总个数 4个操作,这里也规定了子类必须按照这样的声明去实现这几个操作。
其次,注意到static HashTable* create(int keyType);
,说明很大可能使用这个函数来创建哈希表,并且这里的返回值是 HashTable*
,但HashTable
是抽象类,不会有对象,这里的指针应该指向派生类 BasicHashTable 的对象。函数参数 keyType 说明创建哈希表需要指定键值类型,HashTable.hh给出了两个键值类型:
int const STRING_HASH_KEYS = 0; int const ONE_WORD_HASH_KEYS = 1;
再者,HashTable 类声明了一个迭代器类 Iterator ,并且要求传入哈希表引用,应该是用来遍历哈希表的。
最后就是 RemoveNext 操作删除一个哈希表元素,getFirst 操作获取第一个哈希表元素。
🎄三、BasicHashTable 类
BasicHashTable 类是哈希表的具体实现,它实现了哈希表的基本操作:插入、删除、查询。也实现了哈希函数、键值比对、哈希表扩容等函数,不过这些都是隐藏(private)的。
BasicHashTable 类声明如下:
class BasicHashTable: public HashTable { private: class TableEntry; // forward public: BasicHashTable(int keyType); virtual ~BasicHashTable(); // Used to iterate through the members of the table: class Iterator; friend class Iterator; // to make Sun's C++ compiler happy class Iterator: public HashTable::Iterator {// 迭代器,用于迭代传入的哈希表 2024-07-22 23:43:05 public: Iterator(BasicHashTable const& table); private: // implementation of inherited pure virtual functions void* next(char const*& key); // returns 0 if none private: BasicHashTable const& fTable; unsigned fNextIndex; // index of next bucket to be enumerated after this TableEntry* fNextEntry; // next entry in the current bucket }; private: // implementation of inherited pure virtual functions // 实现继承的纯虚函数,这里是 private 的,也就是说不能通过 BasicHashTable 对象直接调用,但可以通过父类指针或引用来多态调用 2024-07-24 virtual void* Add(char const* key, void* value); // Returns the old value if different, otherwise 0 virtual Boolean Remove(char const* key); virtual void* Lookup(char const* key) const; // Returns 0 if not found virtual unsigned numEntries() const; private: class TableEntry { public: TableEntry* fNext; char const* key; void* value; }; TableEntry* lookupKey(char const* key, unsigned& index) const; // returns entry matching "key", or NULL if none Boolean keyMatches(char const* key1, char const* key2) const; // used to implement "lookupKey()" TableEntry* insertNewEntry(unsigned index, char const* key); // creates a new entry, and inserts it in the table void assignKey(TableEntry* entry, char const* key); // used to implement "insertNewEntry()" void deleteEntry(unsigned index, TableEntry* entry); void deleteKey(TableEntry* entry); // used to implement "deleteEntry()" void rebuild(); // rebuilds the table as its size increases unsigned hashIndexFromKey(char const* key) const; // used to implement many of the routines above unsigned randomIndex(uintptr_t i) const { return (unsigned)(((i*1103515245) >> fDownShift) & fMask); } private: TableEntry** fBuckets; // pointer to bucket array TableEntry* fStaticBuckets[SMALL_HASH_TABLE_SIZE];// used for small tables unsigned fNumBuckets, fNumEntries, fRebuildSize, fDownShift, fMask; int fKeyType; };
首先,BasicHashTable类继承自HashTable类,并且实现了继承的全部纯虚函数,所以BasicHashTable类不是抽象类,可以实例化对象。BasicHashTable类有点特别,只提供了创建对象接口(BasicHashTable
)、销毁对象接口(~BasicHashTable
),其他函数都是私有的,即使构造了对象,也没有公有接口可以使用,让用户只能通过基类(HashTable)指针或引用去使用基类声明为公有的几个纯虚函数,然后通过多态调用到 BasicHashTable 类的相应接口。
构造函数:
#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; } }
哈希表最初创建时,只是用个包含3个元素的数组。
在阅读下面小节之前,先了解 BasicHashTable 存储键值对的结构体,除了key、value,还包含了一个 fNext 指针:
class TableEntry { public: TableEntry* fNext; char const* key; void* value; };
✨3.1 插入操作
BasicHashTable类插入操作通过 Add 函数实现,代码如下:
// 添加一个键值对到哈希表,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; }
先查找 key 值是否已存在了,是的话就替换并返回旧的value值,不存在就插入新的键值对(insertNewEntry)。下面看看Add依赖的几个函数:lookupKey、hashIndexFromKey、keyMatches、insertNewEntry、assignKey、rebuild。
lookupKey 函数:根据key找到一个键值对(entry),下标index
// 根据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; }
先计算出哈希地址(hashIndexFromKey),再比对键值,找到键值对 entry。
hashIndexFromKey函数:哈希函数,根据key生成哈希地址index
// 哈希函数,根据key生成一个下标 2024-07-22 23:07:25 unsigned BasicHashTable::hashIndexFromKey(char const* key) const { unsigned result = 0; if (fKeyType == STRING_HASH_KEYS) { while (1) { char c = *key++; if (c == 0) break; result += (result<<3) + (unsigned)c; } result &= fMask; printf("result = %d\n",result); } else if (fKeyType == ONE_WORD_HASH_KEYS) { result = randomIndex((uintptr_t)key); } else { unsigned* k = (unsigned*)key; uintptr_t sum = 0; for (int i = 0; i < fKeyType; ++i) { sum += k[i]; } result = randomIndex(sum); } return result; }
按照不同键值类型去生成哈希地址。
keyMatches 函数:比对两个键值是否相等,相等返回true。
// 比较两个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; } }
insertNewEntry函数:生成一个entry, 插入到链表,并给entry->key赋值
// 生成一个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; }
这里使用头插法,将新的entry插入到 fBuckets[index] 的位置。
assignKey函数: 根据键值类型、key值,创建一个 Key,并赋值到entry的key字段
// 根据键值类型、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; } }
rebuild 函数:重新建立一个哈希表
// 重新建立一个哈希表,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); hPtr->fNext = fBuckets[index]; fBuckets[index] = hPtr; } } // Free the old bucket array, if it was dynamically allocated: if (oldBuckets != fStaticBuckets) delete[] oldBuckets; }
当哈希表键值对个数太多时,就会重建哈希表,避免因个数太多降低查询效率。
✨3.2 删除操作
BasicHashTable 的删除操作通过 Remove 函数实现,代码如下:
// 删除一个键值对(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; }
1、先根据key找到键值对entry、index;
2、再删除键值对 (deleteEntry)。
deleteEntry 函数:删除指定下标的一个键值对(Entry)
// 删除指定下标的一个键值对(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; }
1、先找到存在数组的位置;
2、遍历链表,找到键值对entry;
3、删除键值(deleteKey);
deleteKey函数:删除一个键值对(Entry)的Key
// 删除一个键值对(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; } }
✨3.3 查询操作
BasicHashTable 的查询操作通过 Lookup 函数实现,代码如下:
// 查找,根据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; }
通过key找到键值对entry,然后将value返回。
✨3.4 查询哈希表元素个数
BasicHashTable 的查询元素个数通过 numEntries 函数实现,代码如下:
// 哈希表总的键值对(entry)个数,2024-07-22 23:47:35 unsigned BasicHashTable::numEntries() const { return fNumEntries; }
🎄四、哈希表的使用
这个小节,写个示例来使用上面介绍的哈希表,完整源码也上传了。下载地址:https://download.csdn.net/download/wkd_007/89576315
// g++ *.cpp -o HashTest #include <iostream> #include "BasicHashTable.hh" using namespace std; void printHashTable(HashTable const& hashTable) { HashTable::Iterator *itor = HashTable::Iterator::create(hashTable); void* value = NULL; const char* pKey = NULL; while((value = itor->next(pKey)) != NULL) { const char* value_str = (const char*)value; cout << "Key=" << pKey << ", Value=" << value_str << endl; } delete itor; } int main() { HashTable *pHashTable = new BasicHashTable(STRING_HASH_KEYS); pHashTable->Add("testA",(void*)"testA"); pHashTable->Add("testB",(void*)"testB"); pHashTable->Add("testC",(void*)"testC"); pHashTable->Add("testD",(void*)"testD"); pHashTable->Add("testE",(void*)"testE"); pHashTable->Add("",(void*)"testF"); // 空字符串也可以 const char *pTestA = (const char*)pHashTable->Lookup("testA"); cout << "testA=" << pTestA << endl; cout << endl; printHashTable(*pHashTable); cout << endl; pHashTable->Add("",(void*)"testG"); // 替换空字符串的值 printHashTable(*pHashTable); cout << endl; delete pHashTable; return 0; }
🎄五、总结
👉本文介绍了Live555的哈希表实现,最后给出了使用例子,对于想了解哈希表实现或Live555源码的同学有一定的帮助。
如果文章有帮助的话,点赞👍、收藏⭐,支持一波,谢谢 😁😁😁