HashMap、HashTable和Vector的存储扩容解析

HashMap、HashTable和Vector是面试时比较高频问到的知识点，今天就从三个的底层源码的角度分析三者之间的存储、扩容原理和异同点。

HashMap：实现Map接口

                      

实现原理：HashMap采用链地址法。即底层是一个数组实现。数组的每一项（即一个Entry）又是一个链表。结构图如下：

每个Entry是一个键值对。源码如下：

1. 1. transient Entry[] table;
2. 2.
3. 3. static class Entry<K,V> implements Map.Entry<K,V> {
4. 4. final K key;
5. 5. V value;
6. 6. Entry<K,V> next;
7. 7. final int hash;
8. 8. ……
9. 9. }

HashMap的存储机制：首先根据key计算出该key对应的Entry在数组中的位置，然后判断是否该Entry是否在该位置对应的链表中，如果不在，则插入链表的头部，如果在，则更新该链表中对应Entry的value。

HashMap计算key所属数组的位置方法：首先计算key的hash值，然后根据hash函数hashcode & (length - 1)计算出所在数组的位置（因为HashMap的数组长度为2的整数幂，所以采用位运算的结果和hash % length相同，但是位运算的效率要远高于求余运算）。源码如下：

1. 1. static int indexFor(int h, int length) {
2. 2. return h & (length- 1);
3. 3. }

HashMap的扩容：每当初始化一个HashMap，默认的数组大小（table.size）为16，默认的增长因子（loadFactor）为0.75,；当元素个数超过数组大小的loadFactor   时，就会 对数组进行扩容。HashMap采用的扩容方法为：每次把数组大小扩大一倍，然后重新计算HashMap中每个元素在数组中的位置。也可以   自定义扩展容量的大小（ HashMap(int initialCapacity)）。

HashTable：实现了Map接口，同时也是Dictionary抽象类的具体实现。

HashTable通过Synchronize实现线程安全。实现原理与HashMap相同，也是采用数组+链表的结构实现。不同于HashMap的是：

1) HashTable的默认大小为11

2) 数组位置的计算方法不同；HashTable的 index = (hashcode & Integer.MAX_VALUE) % table.length

3) 扩容的方法不一样；newlength = oldlength * 2 + 1

4) 在使用中，HashTable不允许key值为null，也不允许value为null

Vector：实现了List接口，是一个用Synchronize修饰的线程安全的动态数组。

扩容方法：

1，计算新容量大小。NewSize = oldSize + (Increment>0 ) ? Increment:oldSize。（如果增长因子小于零，每次扩容大小为增长前的一倍，如果增长因子大于零，则每次扩容大小为增长因子的大小）

 2，判断新容量大小和最小需求大小。如果小于最小需求，则把最小需求容量复制给新容量。

3，如果新容量大小大于数组最大容量，则判断最小需求大小和最大数组容量大小；如果最小需求大小大于最大数组容量，则最终新容量为Integer.MaxValue，反之则最终新容量大小为最大数组容量(最大数组容量 = Integer.MaxValue-8）。

设置第三步的原因：vector的增长不是无节制的。Vector的最大长度限制为Integer.MaxValue，所以在第二步计算出新容量大小后，需要比较新容量大小和最大数组容量大小，如果大于，则对最小需求容量调用最终容量计算函数来求出最终的容量。

源码分析：

1. /**
2. * This implements the unsynchronized semantics of ensureCapacity.
3. * Synchronized methods in this class can internally call this
4. * method for ensuring capacity without incurring the cost of an
5. * extra synchronization.
6. *
7. * @see #ensureCapacity(int)
8. */
9. private void ensureCapacityHelper(int minCapacity) {
10. // overflow-conscious code
11. if (minCapacity - elementData.length > 0)
12. grow(minCapacity);
13. }
15. /**
16. * The maximum size of array to allocate.
17. * Some VMs reserve some header words in an array.
18. * Attempts to allocate larger arrays may result in
19. * OutOfMemoryError: Requested array size exceeds VM limit
20. */
21. private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
23. private void grow(int minCapacity) {
24. // overflow-conscious code
25. int oldCapacity = elementData.length;
26. //步骤一 设置新容量
27. int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
28. capacityIncrement : oldCapacity);
29. //步骤二 比较新容量和需求容量
30. if (newCapacity - minCapacity < 0)
31. newCapacity = minCapacity;
32. //步骤三 保证Vector不会不限制增长
33. if (newCapacity - MAX_ARRAY_SIZE > 0)
34. newCapacity = hugeCapacity(minCapacity);
35. elementData = Arrays.copyOf(elementData, newCapacity);
36. }
38. private static int hugeCapacity(int minCapacity) {
39. if (minCapacity < 0) // overflow
40. throw new OutOfMemoryError();
41. return (minCapacity > MAX_ARRAY_SIZE) ?
42. Integer.MAX_VALUE :
43. MAX_ARRAY_SIZE;
44. }