##扯数据结构 先看一下哈希表的概念: 哈希表是一种数据结构,它可以提供快速的插入操作和查找操作。第一次接触哈希表,他会让人难以置信,因为它的插入和删除、查找都接近O(1)的时间级别。用哈希表,很多操作都是一瞬间的事情。 哈希表也有一些缺点: 它基于数组的,数组创建后难以扩展。某些哈希表被基本填满时,性能下降的非常严重。 学习数据结构难免是枯燥的,如果有一个最佳模板供我们参考,那么学起来就会事半功倍了。题外:最佳模板就是一个强力的Demo。 我学到的数据结构,在Java中都有最佳模板来参考。比如: - 数组是Array - 链表是LinkedList - 队列是Queue,一般用实现类LinkedList - 优先级队列是ProirityQueue - 归并排序是Arrays.sort() - 二叉树是TreeList,TreeList不在Java开发包中,在commons-collections.jar中,他用到的是AVL树 而分析哈希表,最佳模板无疑是HashMap了。 **编写Java开发包都是一群神人,拿Java源码来分析问题,我们无疑站在了巨人的肩膀上。所谓站得高,尿的远也。当然,所谓偷拍都是避免不了的。** ##开整HashMap 哈希表为解决冲突,采用了开发地址法和链地址法来解决问题。Java中HashMap采用了链地址法。 链地址法,简单来说,就是数组加链表的结合。在每个数组元素上都一个链表结构,当数据被hash后,得到数组下标,把数据放在对应下标元素的链表上。所以HashMap插入的速度特别快,读取的速度也特别快。当然为了防止数据聚集在一起,HashMap采取了一定的措施。 一张图,可以大概说明HasnMap的结构: ![HasnMap的结构](http://dl.iteye.com/upload/attachment/364590/1c28849c-b67c-3461-b48f-54bd4b023b53.jpg) 当然,我们可以深入源码来看结构,更有说服力。 我们先从HashMap的构造函数入手,进而引出他的数据结构: ###构造一 ```java public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); // Find a power of 2 >= initialCapacity int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; this.loadFactor = loadFactor; threshold = (int)(capacity * loadFactor); table = new Entry[capacity]; init(); } ``` `capacity `是数组的初始大小 `loadFactor` 是负载因子(负载因子越大,容量扩容的边界越大) `threshold` 是数组扩容的边界 (=capacity *loadFactor) 当我们使用这个构造的时候,会指定数组的初始大小和负载因子。而关于`threshold`的作用,后面我们在`resize(int newCapacity)`方法中会讲到。在这个构造函数中,我们看到了HashMap使用到的数据结构,就是一个Entry的数组,Entry是HashMap内部静态类,他其实就是一个链表。关于这个类,我们在讨论完构造函数后再讲。 构造一我们还需要关注这一段: ```java int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; ``` 这段代码告诉我们,数组的大小不是我们指定的值,而是一个2的倍数。比如我们给`initialCapacity`的值为9,那么数组的大小其实为16. ###构造二 ```java public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } ``` `DEFAULT_LOAD_FACTOR`的大小是0.75,构造二调用了构造一。 ###构造三 ```java public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); table = new Entry[DEFAULT_INITIAL_CAPACITY]; init(); } ``` 构造三是默认构造函数,`DEFAULT_INITIAL_CAPACITY `的值是16。他没有调用构造一,而是直接创建了数据结构Entry。 ###构造四 ```java public HashMap(Map<? extends K, ? extends V> m) { this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); putAllForCreate(m); } ``` 构造四先不急讲,看完下面的内容,我们自己就能够读懂`putAllForCreate(m);`方法了。 ##数据结构之Entry数组 前面已经讲过HashMap的结构,我们在构造函数中,也能看出端倪。那么Entry类到底是干嘛用的呢?其实他就是一个单向链表,看源码就明白了: ```java static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; final int hash; ... ... } ``` 它保存了一个key,一个value,指向下一节点的next应用,和一个hash值。 ##HashMap之put方法 HashMap通过构造函数创建了一个数据模型,我们可以在这个模型中添加数据,然后操作数据,使用数据。当然,我们操作的前提是先添加,所以`put(K key, V value)`方法请看过来: ```java public V put(K key, V value) { if (key == null) return putForNullKey(value); int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, key, value, i); return null; } ``` 这个方法涉及主要方法有4个,我们一一来分析。 首先,`key`为空要调用`putForNullKey(value);`方法: ```java private V putForNullKey(V value) { for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(0, null, value, 0); return null; } ``` 我们看到,`null`为key的值会被放在数组的第一个元素上。如果第一个元素已经存在`null`为key的值,那么进行替换。 如果第一个元素上还没有`null`为key的值,那么调用`addEntry(0, null, value, 0);`方法将`null`的key将被放在第一个元素上。 关于`addEntry(0, null, value, 0);`方法,我们需要返回到`put(K key, V value)`来继续看。 ---------- 哈希表的核心之一是哈希函数,好的哈希函数可以让数据分布的更均匀,从而使哈希表的结构达到优化。 我们看`put(K key, V value)`中是如何进行hash的,他调用了`hash(key.hashCode());`: ```java static int hash(int h) { // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } ``` 首先,调用了`key.hashCode()`方法,然后对hashCode进行再次hash。为什么要再次hash呢?是为了散列,为了让0、1分布更加均匀。而关于`hashCode()`方法,我们可以参考String类: ```java public int hashCode() { int h = hash; if (h == 0) { int off = offset; char val[] = value; int len = count; for (int i = 0; i < len; i++) { h = 31*h + val[off++]; } hash = h; } return h; } ``` Java以31为底进行的hash,c++中以33为底,这是前辈们总结出的最佳方案。 ---------- `put(K key, V value)`在进行二次hash之后,调用了`indexFor(hash, table.length);`: ```java static int indexFor(int h, int length) { return h & (length-1); } ``` 这个函数是为了获取小于数组长度的一个下标。 ---------- 然后`put(K key, V value)`进行了`putForNullKey(value);`方法相似的操作,如果数组元素存在以当前key,那么替换他的value值。 如果不存在,则调用`addEntry(hash, key, value, i);`方法: ```java void addEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<K,V>(hash, key, value, e); if (size++ >= threshold) resize(2 * table.length); } ``` 重头戏来了,我们来看一下这个方法。 其实他的内部实现也不复杂,就是在对应的下标元素中放入了一个节点,节点中保存了key、value、下一个节点的引用和key的hash值。 在保存元素之后,他检查了一下容器的容量,如果容量大于或等于容量边界,那么进行扩容,扩容的规模是当前容量的2倍,看`resize(2 * table.length);`方法: ```java void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; transfer(newTable); table = newTable; threshold = (int)(newCapacity * loadFactor); } ``` `resize(int newCapacity) `进行了例行判断,然后创建了一个大一倍的容器,它调用`transfer(newTable);`方法把旧容器的数据再次哈希分配到了新容器: ```java void transfer(Entry[] newTable) { Entry[] src = table; int newCapacity = newTable.length; for (int j = 0; j < src.length; j++) { Entry<K,V> e = src[j]; if (e != null) { src[j] = null; do { Entry<K,V> next = e.next; int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); } } } ``` `transfer(Entry[] newTable) `方法内部不复杂,只是进行了再次哈希而已,可参考`put(K key, V value)`方法。 ---------- 至此,HashMap的真容尽露,我们回头看`构造四`就不困难了。 同时,我们对哈希表这种数据结构也有了相对透彻的理解。 ##HashMap之使用 首先我们要明白,HashMap不是线程安全的,如果在多线程中使用,可能出现死循环,造成CPU100%。解决方案是使用`Collections.synchronizedMap()`把Map变成线程安全的。不推荐使用HashTable。 其次,HashMap大小是固定的,他扩容的速度是自身size的两倍。如果用HashMap承载大数据,那么我们应该给与他较大的初始容器大小。例如,有50000数据,我们最好不要使用HashMap的默认构造函数了。 最后,差点忘了说了:如果使用自定义的类当Map的key的话,记得一定要在类中重写`hashCode()`方法。
> *本文使用 [Cmd](http://ghosertblog.github.io/mdeditor/ "中文在线 Markdown 编辑器") 编写* [1]: http://dl.iteye.com/upload/attachment/364590/1c28849c-b67c-3461-b48f-54bd4b023b53.jpg