背景

Java 和 .Net 平台都有一个所有引用类型都会间接或直接继承的类型：Object，这个类型提供最基本的相等性比较算法和哈希算法，很多书上都给出了在重写这两个算法的时候的主意事项，其中大多数主意事项都和哈希表有关。

《CLR VIA C#》的作者觉得将哈希算法放到 Object 不是很适合，我也有这种感觉，每次重写相等性比较算法都要重新哈希算法，非常不爽，我就没打算将其用到哈希表中作为键使用。

哈希表

定义

使用哈希算法将 A 数值空间（键）映射到 B 数值空间（存储），如下：

A -> 0

B -> 1

C -> 2

D -> 3

B 数值空间的查询速度要求非常快，毫无疑问就是数值了。

冲突

数组的大小是固定，当出现冲突（两个键映射为同一个数值了）的时候如何处理呢？有两种策略：

• 在数组中按照一定的算法继续探测其它地址。
• 在数组的每个元素存储的都是链表，冲突的元素会被插入到链表中。

实现

链表节点

1         class Node
     
      2         {3             public TKey Key { get; set; }4 5             public TValue Value { get; set; }6 7             public Node
      
        Next { get; set; }8         }
      
     

链表

1         class LinkedList
     
       2         { 3             public Node
      
        First { get; set; } 4  5             public void Insert(TKey key, TValue value) 6             { 7                 if (this.Contains(key)) 8                 { 9                     throw new InvalidOperationException("不能插入重复的键");10                 }11 12                 var node = new Node
       
         { Key = key, Value = value };13                 node.Next = this.First;14                 this.First = node;15             }16 17             public void Delete(TKey key)18             {19                 Node
        
          parent;20                 Node
         
           node;21 22                 if (!this.Find(key, out   parent, out  node))23                 {24                     throw new InvalidOperationException("不存在指定的键");25                 }26 27                 if (parent == null)28                 {29                     this.First = null;30                 }31                 else32                 {33                     parent.Next = node.Next;34                 }35             }36 37             public bool Contains(TKey key)38             {39                 Node
          
            parent;40 Node
           
             node;41 42 return this.Find(key, out parent, out node);43 }44 45 public bool Find(TKey key, out Node
            
              node)46 {47 Node
             
               parent;48 49 return this.Find(key, out parent, out node);50 }51 52 public bool Find(TKey key, out Node
              
                parent, out Node
               
                 node)53 {54 parent = null;55 node = this.First;56 57 while (node != null)58 {59 if (node.Key.Equals(key))60 {61 return true;62 }63 64 parent = node;65 node = node.Next;66 }67 68 return false;69 }70 }
               
              
             
            
           
          
         
        
       
      
     

哈希表

1         class HashTable
     
       2         { 3             private LinkedList
      
       [] _items; 4  5             public HashTable(int size) 6             { 7                 _items = new LinkedList
       
        [size]; 8             } 9 10             public void Insert(TKey key, TValue value)11             {12                 var index = this.HashToIndex(key);13                 if (_items[index] == null)14                 {15                     _items[index] = new LinkedList
        
         ();16                 }17 18                 _items[index].Insert(key, value);19             }20 21             public void Delete(TKey key)22             {23                 var index = this.HashToIndex(key);24                 if (_items[index] == null)25                 {26                     throw new InvalidOperationException("不存在指定的键");27                 }28 29                 _items[index].Delete(key);30             }31 32             public bool Find(TKey key, out TValue value)33             {34                 value = default(TValue);35 36                 var index = this.HashToIndex(key);37                 if (_items[index] == null)38                 {39                     return false;40                 }41 42                 Node
         
           node;43                 var finded = _items[index].Find(key, out  node);44                 if (!finded)45                 {46                     return false;47                 }48                 else49                 {50                     value = node.Value;51                 }52 53                 return true;54             }55 56             private int HashToIndex(TKey key)57             {58                 return key.GetHashCode() % _items.Length;59             }60         }
         
        
       
      
     

备注

哈希算法、负载因子、自动扩容都是需要考虑的，这里就不多说了。