本文共 2307 字，大约阅读时间需要 7 分钟。

点击上方蓝字关注我，我们一起学编程

微信搜索：编程笔记本

是的，在面试深信服的时候，面试官让我 10min 手写哈希表（/微笑）。没错，我没写出来，于是我自己花了 20*10min 自己写了一个简单的哈希表出来。在这里贴出来，小伙伴可以提提意见，交流一波~

#include 
   
    using namespace std;#define MAXSIZE 10       // 哈希值#define UNIONSIZE 100    // 共用体的字符长度/* 哈希表底层链表节点 */template
    
     struct Node {
       K key;	V value;	struct Node* next;};/* 用于计算哈希值的共用体 */template
     
      union Union {
       K key;	char ch[UNIONSIZE];	Union(K _key) : key(_key) {
   }};/* 哈希表类 */template
      
       class HashTable {
   private:    Node
       
        * node[MAXSIZE];    // 底层链表public:    HashTable();                                // 构造函数	int hash(const K key);                      // 哈希函数	Node
        
         * lookup(const K key); // 查找函数 void insert(const K key, const V value); // 插入函数 V get(const K key); // 访问函数};/* 构造函数 *//* 将哈希表底层链表置空 */template
         
          HashTable
          
           ::HashTable() { for (int i = 0; i < MAXSIZE; ++i) { node[i] = nullptr; }}/* 哈希函数 *//* 简单地利用共用体进行哈希计算 */template
           
            int HashTable
            
             ::hash(const K key) { int hashValue = 0; unsigned int len = sizeof(key) > UNIONSIZE ? UNIONSIZE : sizeof(key); Union
             
               u(key); for (int i = 0; i < len; ++i) { hashValue += u.ch[i]; } return hashValue % MAXSIZE;}/* 查找函数 */template
              
               Node
               
                * HashTable
                
                 ::lookup(const K key) { Node
                 
                  * nd; int hashValue = hash(key); for (nd = node[hashValue]; nd != nullptr; nd = nd->next) { if (nd->key == key) { return nd; } } return nullptr;}/* 插入函数 *//* 若键已存在，则更新值；否则创建新的键值对 */template
                  
                   void HashTable
                   
                    ::insert(const K key, const V value) { Node
                    
                     * nd = lookup(key); if (nd == nullptr) { int hashValue = hash(key); nd = (Node
                     
                      *)malloc(sizeof(Node
                      
                       )); nd->key = key; nd->next = node[hashValue]; node[hashValue] = nd; } nd->value = value;}/* 访问函数 *//* 若键存在，则返回其值；若键不存在，则插入键值对，并将值置为该类型的零值 */template
                       
                        V HashTable
                        
                         ::get(const K key) { V value = (V)(0); Node
                         
                          * nd = lookup(key); if (nd == nullptr) { insert(key, value); nd = lookup(key); } return nd->value;}int main(){ HashTable
                          
                            hashTable; hashTable.insert(1, 100); hashTable.insert(2, 200); cout << hashTable.get(1) << endl; cout << hashTable.get(2) << endl; cout << hashTable.get(3) << endl; return 0;}/*编译运行：jincheng@DESKTOP$ g++ test.cpp -o testjincheng@DESKTOP$ ./test1002000jincheng@DESKTOP$*/
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

小伙伴们有什么好的点子或者意见，记得参与讨论告诉我哦~

微信搜索：编程笔记本