4 手写HashTable底层实现
哈希表存储的是键值对，所以需要两个泛型来分别表示key和value的数据类型，key的数据类型必须实现hashcode()方法，不过由于java中所有的类都继承了Object类，所以默认所有的类都实现了hashcode()方法。
关键在于hashcode()是不是我们想要的。
另外我们也可以考虑哈希表的动态空间处理，当每个位置的平均哈希冲突超过上界时则扩容，小于下界时则缩容。
上面介绍链表法时，整个槽slot可以看做是一个TreeMap数组，数组的每一个位置存储了一个 链表 或者 红黑树，所以构造函数可以实现如下：
public class HashTable<K, V> { /** * 容忍度上界 */ private static final int upperTol = 10; /** * 容忍度下界 */ private static final int lowerTol = 2; /** * 初始容量 */ private static final int initCapacity = 7; private TreeMap<K, V>[] hashtable; // 长度（素数） private int M; // 已经存储了多少元素 private int size; public HashTable(int M){ this.M = M; size = 0; hashtable = new TreeMap[M]; // 对每一个TreeMap进行初始化 for (int i = 0; i < M; i ++) hashtable[i] = new TreeMap<>(); } public HashTable(){ this(initCapacity); } }
在实现哈希表的增删改查之前，我们需要定义辅助方法hash用于计算要存储的位置，由于数组的索引是从0开始的，所以我们要避免负数的出现：
private int hash(K key){ return key.hashCode() & 0x7fffffff % M; } public int getSize(){ return size; }
向哈希表中添加键值对：
1.根据key计算要插入的位置（对应一个TreeMap）
2.如果TreeMap中已经存在这个key的话就进行value的更新
3.如果TreeMap中不存在这个key的话则进行数据添加
4.当元素过多时进行扩容操作
public void add(K key, V value){ // 计算要插入的位置 TreeMap<K, V> map = hashtable[hash(key)]; // key已存在 if (map.containsKey(key)) map.put(key, value); else { // key不存在 map.put(key, value); size ++; // 满足条件则扩容 if (size >= upperTol * M) resize(2 * M); } }
删除操作：
1.根据key计算要删除key对应的位置（对应一个TreeMap）
2.判断是否包含这个key，存在的话则删除
3.当元素过少时进行扩容操作
public V remove(K key){ // 计算要删除的位置 TreeMap<K, V> map = hashtable[hash(key)]; V ret = null; // 存在则删除 if (map.containsKey(key)){ ret = map.remove(key); size --; // 一定情况下缩容 if (size < lowerTol * M && M / 2 >= initCapacity) resize(M / 2); } return ret; }
修改操作：
1.根据key计算要进行修改的位置（对应一个TreeMap）
2.存在该元素时则修改
public void set(K key, V value){ TreeMap<K, V> map = hashtable[hash(key)]; if (!map.containsKey(key)) throw new IllegalArgumentException(key + " doesn't exist!"); map.put(key, value); }
查询操作：
public boolean contains(K key){ return hashtable[hash(key)].containsKey(key); } public V get(K key){ return hashtable[hash(key)].get(key); }
动态空间处理方法：
类似于动态数组，开辟一个新的TreeMap数组，将原始数据全都放入到新的TreeMap数组中即可，注意hash()函数计算时需要使用新的Map长度。
private void resize(int newM){ TreeMap<K, V>[] newHashTable = new TreeMap[newM]; for (int i = 0; i < newM; i ++) newHashTable[i] = new TreeMap<>(); int oldM = M; // hash()函数需要新的M值 this.M = newM; for (int i = 0; i < oldM; i ++){ TreeMap<K, V> map = hashtable[i]; for (K key: map.keySet()) newHashTable[hash(key)].put(key, map.get(key)); } this.hashtable = newHashTable; } }
测试：
读取一本英文著作《傲慢与偏见》，统计词频，查看性能。
public static void main(String[] args) { System.out.println("Pride and Prejudice"); ArrayList<String> words = new ArrayList<>(); if(FileOperation.readFile("pride-and-prejudice.txt", words)){ // HashTable startTime = System.nanoTime(); HashTable<String, Integer> ht = new HashTable<>(131071); for (String word : words) { if (ht.contains(word)) ht.set(word, ht.get(word) + 1); else ht.add(word, 1); } for (String word: words) ht.contains(word); endTime = System.nanoTime(); time = (endTime - startTime)/1000000000.0; System.out.println("HashTable: " + time); } }
执行用时：
5 *应用
有了哈希表我们可以应用于数据可以无序存储但需要快速查询的场景。比如：Word 文档中单词拼写检查功能。
常用的英文单词有 20 万个左右，假设单词的平均长度是 10 个字母，平均一个单词占用 10 个字节的内存空间，那 20 万英文单词大约占 2MB 的存储空间。所以我们可以用散列表来存储整个英文单词词典。
当用户输入某个英文单词时，我们拿用户输入的单词去散列表中查找。如果查到，则说明拼写正确；如果没有查到，则说明拼写可能有误，给予提示。
6 来自阿里师傅的面试题
HashMap的初始容量是16，并且容量都维持在n次方原因：性能考虑。只有2的n次幂的情况时最后一位二进制数才一定是1，这样能最大程度减少hash碰撞（hash值 & length-1）
负载因子越小，内存占用越多，查询时间越快；内存吃紧的话可以调大负载因子，冲突概率会增加。
HashMap对key的要求：不可变的，比如String被final修饰的。
HashMap存在线程安全问题，1.8之前使用头插法会产生环。我们可以使用ConcurrentHashMap来避免线程安全问题。
1.7之前：采用了分段锁机制来储存数据。在集合对象中储存一个segment数组，把集合的元素分为16个分段，每个分段上储存一个HashEntry数组及对应的链表，每个HashEntry数组就相当于一个HashMap。
当触发锁时每一个segment中都会有一个独立的锁，而不会将整个对象锁住，所以多线程操作时每个segment中的数据不会相互影响，从而保证了效率，当然，这样储存的版本还有着不少的问题，如最多并发只有16个，结构过于臃肿等等，随着版本的迭代，在jdk1.8时更改了ConcurrentHashMap的结构，使之更加完善。
1.8之后：利用CAS原理（比较交换原理）解决并发问题，其中有三个数：所存的值V，预期的值A，要变换成为的新值B。当A和V相同时，V会修改成B，否则不进行操作。这样就能较好的解决线程安全的问题。
