HashMap<K,V>
Entry<K,V> table = new Entry<K,V>(expectedNumberOfData);
capacity 表示HashMap底层table数组的长度
threshold 表示阈值 capacity * loadFactor 的值
map.size() 表示 map中实际存的数据的个数
threshold 一定是要和map.size() 进行比较
如果将 key = null 的key-value 值放入到map中，则这个entry在table表中的位置一定是放在 table[0] 的位置
map.size = 黄色部分个数
table.length = 数组实际长度
threshold = 当map中所有的key-value个数超过这个数值时，table将会发生扩容
data_structure.png
**private void inflateTable(int toSize) **
仅限第一次 放入元素时使用，表示将table表扩容到toSize 的大小。首先找到一个 比toSize大的最小的2的幂次，capacity ，则capacity一定是2的幂次。则将table表长变成
table = new Entry<K,V>[capacity];然后相应的阈值发生变化threshold = capacity * loadFactor;static in indexFor(int hash,int tableLength);
通过key的hash值找到 key在表中的位置,tableLength 为2次幂的某个数。首先计算 key的hash值，然后key在table中的最终位置为:
tableIndexOfKey = hash(key) % tableLength。但是在HashMap中 tableIndexOfKey = hash(key) & (tableLength-1)。<b style="background:yellow";>移位操作大大提高效率</b>如何计算key的hash值?
final int hash(key)
- 如果key是string类型 则
sun.misc.Hashing.stringHash32((String) k) 只要key的内容相 同，则key的hash值就相同。 - 如果key不是String类型 则
首先计算key的hashcode，h = key.hashcode();然后h经过移位等操 作得到最终得到hash值。
public V put(K key,V value)
向map中添加元素，过程是这样的:
1)首先判断key-value是否在map中,从底层上来讲就是key-value封装好的entry对象是否在数组-链表中。计算key-value在数组中的位置，tableIndex = hash(key) % table.length,在数组中从tableIndex 处开始找起，那就将key-value和tableIndex处的key-value进行比较。相等的标准：依次遍历tableIndex处链表上的元素，只要判断key。
①：比较两个key的hash值，即hash(key) 也就是key的hashcode 值，如果两个key的hashcode值不相同，则表明这两个key-value相同。
②：如果两个key的hashcode值相同，则需要比较key是否相同，使用equals判断。如果equals判断出，相同，则表明这两个key-value相同，如果这两个key-value不相同，则表明这两个key-value也不相同。
2)如果判断这两个key-value相同，则将新的value替换掉旧的value，并且返回旧的value。
3)如果判断这两个key-value不相同，则考虑增加一个entry对象到table数组中。一个判断的问题：是否需要扩容？
tableIndex为key-value插入的位置
扩容的条件：当所有的key-value个数 size >= 阈值 threshold并且该key-value将要插入的位置 tableIndex目前有元素存在。
4)如果要扩容：目前的table的长度为:oldLength。那么就要将table的长度扩成长度newLength = oldLength*2。然后对原来table中的每一个key-value对象进行重新计算位置。tableIndexNew = hash(key)%newLength;将遍历到原table的元素e，通过头插法插入到tableIndexNew位置的链表上。
e.next = newTable[tableIndexNew]; <b style="background:yellow";>多线程下死循环</b>
newTable[tableIndexNew] = e;
如此以往下去：原table数组 全部扩容 移动到 新table中。
最后重新计算 要插入map中的key-value在新数组中的位置：
tableIndexNew = hash(key)%newLength;
5)如果不需要扩容，则直接将要插入的key-value通过头插法插入到 tableIndex或者tableIndexNew处的链表上。
public V get(Object key)
通过key值获得map中的value值
1）首先计算 带有key的entry对象在数组中的位置：tableIndex = hash(key) % table.length; - 从数组tableIndex处的链表开始定位，向下查找，查找过程判断两个 entry相等的标准（同put方法）
- 返回找到value值
public V remove(Object key)
通过key值删除map中的entry对象
1）首先计算 带有key值的entry对象在数组中的位置：tableIndex = hash(key) % table.length;
2）从数组tableIndex处的链表开始定位，向下查找，查找过程判断两个entry相等的标准（同put方法）
3）定义两个指针，当前指针和previous指针，从链表中删除
<b style="text-decoration:underline";>注：
1）HashMap可以包含 key = null 或者 value = null。当一个key不存在map中，使用map.get(key) 同样返回null。应该使用containsKey(key) 判断map中是否包含key值。HashTable中不允许出现key = null 或者 value = null的key-value。
2）
HashMap extends AbstractMap<K,V>
abstract class AbstractMap<K,V> implements Map<K,V>
Hashtable extends Dictionary<K,V>
abstract class Dictionary<K,V> - HashMap线程非安全 Hashtable 线程安全
HashMap扩容方式 oldLength * 2
Hashtable 扩容方式 oldLength * 2 + 1
HashMap 初始大小 16
Hashtable 初始大小11
</b>
网友评论