哈希表

我们通过将我们要查找的某种数据类型转化为一个索引index，然后通过索引去数组中查找，这时它的复杂度就是O(1)级别的。而将某个数据类型转化为索引的函数我们就称为是哈希函数，比如说将26个小写字母转化为索引，我们可以这么写

  1. index = ch - 'a';

这样就建立起了一一对应的关系，但是并不是所有的对应关系都是一一对应的，因为数组的容量是有限的，而输入的范围可能是无穷的，所以很有可能不同的键对应着同一个索引，比如说键是字符串，因为字符串的组合方式是非常的多，可以看做是无穷的，我们不可能去开辟一个无穷的空间去与这些字符串一一对应，所以不同的字符串生成的索引很有可能会有冲突，我们称这种情况为哈希冲突。由于上面讲到的哈希冲突，所以我们要设计好哈希函数(hashCode())使得发生哈希冲突的可能性小，即使哈希函数产生的哈希值均匀的分布在数组中。

哈希函数的设计

哈希函数应该满足上面提到的：哈希函数产生的哈希值均匀的分布在数组中。数据的类型五花八门，对于特殊的领域有特殊领域的哈希函数的设计方式，甚至还有专门的论文，说这么多就是想说哈希函数的设计十分的复杂，在这里我们只提最简单的一种，哈希函数的设计应该满足

  • 一致性
    • 如果a == b，那么hashCode(a) == hashCode(b)
  • 高效性
    • 计算迅速
  • 均匀性
    • 输出尽可能均匀

哈希表 - 图1
由于Java中基本数据类型和字符串类型有默认的hashCode()计算，所以我们就用Java自带的hashCode计算基本数据类型和字符串的哈希值，而对于引用类型Java是根据地址计算的哈希值，所以可能会出现问题，需要我们自己自定义规则，比如对于一个Student类，我们规定学号以及姓名相同(不区分大小写)就是同一个学生，所以根据一致性原则，它们应该产生相同的哈希值，但是由于Java默认是根据地址产生哈希值，由于二者的地址是不同的，所以产生的哈希值有极大的概率是不同的，所以我们需要自己创建哈希函数。

链地址法

现在我们来演示往哈希表中添加元素的步骤
哈希表 - 图2

  1. import java.util.TreeMap;
  3. public class HashTable<K, V> {
  4.     //数组中存储的是TreeMap这种查找表
  5.     private TreeMap<K, V>[] hashTable;
  6.     private int M;
  7.     private int size;
  9.     public HashTable(int M) {
  10.         this.M = M;
  11.         size = 0;
  12.         hashTable = new TreeMap[M];
  14.         for (int i = 0; i < hashTable.length; i++) {
  15.             hashTable[i] = new TreeMap<>();
  16.         }
  17.     }
  19.     public HashTable() {
  20.         this(97);
  21.     }
  23.     public int getSize() {
  24.         return size;
  25.     }
  27.     //得到在数组中的索引
  28.     private int hash(K key) {
  29.         //与0x7fffffff是为了消除负数
  30.         return (key.hashCode() & 0x7fffffff) % M;
  31.     }
  33.     public void add(K key, V value) {
  34.         TreeMap<K, V> map = hashTable[hash(key)];
  35.         //先查看已经是否有这个键了
  36.         if (map.containsKey(key)) {
  37.             //有则更新
  38.             map.put(key, value);
  39.         } else {
  40.             //没有则进行添加，并维护size
  41.             map.put(key, value);
  42.             size++;
  43.         }
  44.     }
  46.     public V remove(K key, V value) {
  47.         V ret = null;
  48.         TreeMap<K, V> map = hashTable[hash(key)];
  49.         //如果包含键则删除，没有返回null
  50.         if (map.containsKey(key)) {
  51.             ret = map.remove(key);
  52.             size--;
  53.         }
  55.         return ret;
  56.     }
  58.     public void set(K key, V value) {
  59.         TreeMap<K, V> map = hashTable[hash(key)];
  60.         //没有该键抛出异常
  61.         if (!map.containsKey(key)) {
  62.             throw new IllegalArgumentException("键不存在");
  63.         }
  65.         map.put(key,value);
  66.     }
  68.     //直接得到相应的TreeMap，然后去查，TreeMap有检查步骤
  69.     public V get(K key) {
  70.         return hashTable[hash(key)].get(key);
  71.     }
  72. }

哈希表 - 图3

  1. import java.util.TreeMap;
  3. public class HashTable<K, V> {
  4.     private static final int upperTol = 10;
  5.     private static final int lowerTol = 2;
  6.     private static final int initCapacity = 7;
  8.     //数组中存储的是TreeMap这种查找表
  9.     private TreeMap<K, V>[] hashTable;
  10.     private int M;
  11.     private int size;
  13.     public HashTable(int M) {
  14.         //只显示改变的内容
  15.         //...
  16.         hashTable = new TreeMap[initCapacity];
  17.     }
  19.     public void add(K key, V value) {
  20.         //...
  22.         if (size >= upperTol * M) {
  23.             resize(2 * M);
  24.         }
  25.     }
  27.     public V remove(K key, V value) {
  28.         //...
  30.         if (size < M * lowerTol && M / 2 >= initCapacity) {
  31.             resize(M / 2);
  32.         }
  34.         return ret;
  35.     }
  37.     private void resize(int newM) {
  38.         TreeMap<K,V>[] newHashTable = new TreeMap[newM];
  40.         //后面要更新M，但是还需要旧M遍历数组
  41.         int oldM = M;
  42.         //由于后面要重新计算下标，所以这里要更新M
  43.         M = newM;
  45.         for (int i = 0; i < oldM; i++) {
  46.             TreeMap<K, V> map = hashTable[i];
  47.             for (K key: map.keySet()) {
  48.                 //重新计算下标并赋值
  49.                 newHashTable[hash(key)].put(key, map.get(key));
  50.             }
  51.         }
  53.         hashTable = newHashTable;
  54.     }
  55. }

但是我们发现每次我们都扩容为2 * M，这时M就不是一个素数了，为了解决这一个问题，我们准备一个素数表，让M取素数表中的值，每次扩容M在素数表中的索引+1，缩容-1

  1. import java.util.TreeMap;
  3. public class HashTable<K, V> {
  4.     //素数表
  5.     private static final int[] capacity = {};
  6.     private static final int upperTol = 10;
  7.     private static final int lowerTol = 2;
  8.     private  int capacityIndex = 0;
  10.     //数组中存储的是TreeMap这种查找表
  11.     private TreeMap<K, V>[] hashTable;
  12.     private int M;
  13.     private int size;
  15.     public HashTable() {
  16.         this.M = capacity[capacityIndex];
  17.         size = 0;
  18.         hashTable = new TreeMap[M];
  20.         for (int i = 0; i < hashTable.length; i++) {
  21.             hashTable[i] = new TreeMap<>();
  22.         }
  23.     }
  25.     public void add(K key, V value) {
  26.         //...
  27.         if (size >= upperTol * M && capacityIndex + 1 < size) {
  28.             capacityIndex++;
  29.             resize(capacity[capacityIndex]);
  30.         }
  31.     }
  33.     public V remove(K key, V value) {
  34.         //...
  36.         if (size < M * lowerTol && capacityIndex - 1 >= 0) {
  37.             capacityIndex--;
  38.             resize(capacity[capacityIndex]);
  39.         }
  41.         return ret;
  42.     }
  43. }

完整代码

  1. import java.util.TreeMap;
  3. public class HashTable<K, V> {
  4.     private static final int[] capacity = {};
  5.     private static final int upperTol = 10;
  6.     private static final int lowerTol = 2;
  7.     private  int capacityIndex = 0;
  9.     //数组中存储的是TreeMap这种查找表
  10.     private TreeMap<K, V>[] hashTable;
  11.     private int M;
  12.     private int size;
  14.     public HashTable() {
  15.         this.M = capacity[capacityIndex];
  16.         size = 0;
  17.         hashTable = new TreeMap[M];
  19.         for (int i = 0; i < hashTable.length; i++) {
  20.             hashTable[i] = new TreeMap<>();
  21.         }
  22.     }
  24.     public int getSize() {
  25.         return size;
  26.     }
  28.     //得到在数组中的索引
  29.     private int hash(K key) {
  30.         //与0x7fffffff是为了消除负数
  31.         return (key.hashCode() & 0x7fffffff) % M;
  32.     }
  34.     public void add(K key, V value) {
  35.         TreeMap<K, V> map = hashTable[hash(key)];
  36.         //先查看已经是否有这个键了
  37.         if (map.containsKey(key)) {
  38.             //有则更新
  39.             map.put(key, value);
  40.         } else {
  41.             //没有则进行添加，并维护size
  42.             map.put(key, value);
  43.             size++;
  44.         }
  46.         if (size >= upperTol * M && capacityIndex + 1 < capacity.length) {
  47.             capacityIndex++;
  48.             resize(capacity[capacityIndex]);
  49.         }
  50.     }
  52.     public V remove(K key, V value) {
  53.         V ret = null;
  54.         TreeMap<K, V> map = hashTable[hash(key)];
  55.         //如果包含键则删除，没有返回null
  56.         if (map.containsKey(key)) {
  57.             ret = map.remove(key);
  58.             size--;
  59.         }
  61.         if (size < M * lowerTol && capacityIndex - 1 >= 0) {
  62.             capacityIndex--;
  63.             resize(capacity[capacityIndex]);
  64.         }
  66.         return ret;
  67.     }
  69.     public void set(K key, V value) {
  70.         TreeMap<K, V> map = hashTable[hash(key)];
  71.         //没有该键抛出异常
  72.         if (!map.containsKey(key)) {
  73.             throw new IllegalArgumentException("键不存在");
  74.         }
  76.         map.put(key,value);
  77.     }
  79.     //直接得到相应的TreeMap，然后去查，TreeMap有检查步骤
  80.     public V get(K key) {
  81.         return hashTable[hash(key)].get(key);
  82.     }
  84.     private void resize(int newM) {
  85.         TreeMap<K,V>[] newHashTable = new TreeMap[newM];
  87.         //后面要更新M，但是还需要旧M遍历数组
  88.         int oldM = M;
  89.         //由于后面要重新计算下标，所以这里要更新M
  90.         M = newM;
  92.         for (int i = 0; i < oldM; i++) {
  93.             TreeMap<K, V> map = hashTable[i];
  94.             for (K key: map.keySet()) {
  95.                 //重新计算下标并赋值
  96.                 newHashTable[hash(key)].put(key, map.get(key));
  97.             }
  98.         }
  100.         hashTable = newHashTable;
  101.     }
  102. }