国内专门做旅游攻略的网站/香港百度广告

int threshold;             // 所能容纳的key-value对极限 
final float loadFactor;    // 负载因子
int modCount;  
int size;复制代码

• 新建一个 HashMap，默认大小为 16；
• 插入 <K1,V1> 键值对，先计算 K1 的 hashCode 为 115，使用除留余数法得到所在的桶下标 115%16=3。
• 插入 <K2,V2> 键值对，先计算 K2 的 hashCode 为 118，使用除留余数法得到所在的桶下标 118%16=6。
• 插入 <K3,V3> 键值对，先计算 K3 的 hashCode 为 118，使用除留余数法得到所在的桶下标 118%16=6，插在 <K2,V2> 前面。

• 计算键值对所在的桶；
• 在链表上顺序查找，时间复杂度显然和链表的长度成正比。

x   : 00010000
x-1 : 00001111
复制代码

y       : 10110010
x-1     : 00001111
y&(x-1) : 00000010复制代码

y   : 10110010
x   : 00010000
y%x : 00000010复制代码

public V put(K key, V value) {// 对key的hashCode()做hashreturn putVal(hash(key), key, value, false, true);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;// 步骤1：tab为空则创建if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 步骤2：计算index，并对null做处理 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null);else {Node<K,V> e; K k;// 步骤3：节点key存在，直接覆盖valueif (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;// 步骤4：判断该链为红黑树else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);// 步骤5：该链为链表else {for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key,value,null);//链表长度大于8转换为红黑树进行处理if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st  treeifyBin(tab, hash);break;}// key已经存在直接覆盖valueif (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))) break;p = e;}}if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;// 步骤6：超过最大容量 就扩容if (++size > threshold)resize();afterNodeInsertion(evict);return null;}复制代码

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;
}复制代码

void addEntry(int hash, K key, V value, int bucketIndex) {if ((size >= threshold) && (null != table[bucketIndex])) {resize(2 * table.length);hash = (null != key) ? hash(key) : 0;bucketIndex = indexFor(hash, table.length);}createEntry(hash, key, value, bucketIndex);
}void createEntry(int hash, K key, V value, int bucketIndex) {Entry<K,V> e = table[bucketIndex];// 头插法，链表头部指向新的键值对table[bucketIndex] = new Entry<>(hash, key, value, e);size++;
}Entry(int h, K k, V v, Entry<K,V> n) {value = v;next = n;key = k;hash = h;
}
复制代码

2.3. 扩容-基本原理

和扩容相关的参数主要有：capacity、size、threshold 和 load_factor。

void addEntry(int hash, K key, V value, int bucketIndex) {Entry<K,V> e = table[bucketIndex];table[bucketIndex] = new Entry<>(hash, key, value, e);if (size++ >= threshold)resize(2 * table.length);
}复制代码

void resize(int newCapacity) {   //传入新的容量Entry[] oldTable = table;    //引用扩容前的Entry数组int oldCapacity = oldTable.length;         if (oldCapacity == MAXIMUM_CAPACITY) {  //扩容前的数组大小如果已经达到最大(2^30)了threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了return;}Entry[] newTable = new Entry[newCapacity];  //初始化一个新的Entry数组transfer(newTable);                         //将数据转移到新的Entry数组里table = newTable;                           //HashMap的table属性引用新的Entry数组threshold = (int)(newCapacity * loadFactor);//修改阈值
}
复制代码

• hashmap不是线程安全的、hashtable是安全的
• HashMap允许将 null 作为一个 entry 的 key 或者 value，而 Hashtable 不允许。
• HashMap 把 Hashtable 的 contains 方法去掉了，改成 containsValue 和 containsKey。因为 contains 方法容易让人引起误解。
• HashTable 继承自 Dictionary 类，而 HashMap 是 Java1.2 引进的 Map interface 的一个实现。
• HashTable 的方法是 Synchronized 的，而 HashMap 不是，在多个线程访问 Hashtable 时，不需要自己为它的方法实现同步，而 HashMap 就必须为之提供外同步，或者改为使用ConcurrentHashMap。
  
• Hashtable 和 HashMap 采用的 hash/rehash 算法都大概一样，所以性能不会有很大的差异。
• HashMap 不能保证随着时间的推移 Map 中的元素次序是不变的。
• HashMap 的迭代器是 fail-fast 迭代器。

1. 扩容是一个特别耗性能的操作，所以当程序员在使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容。
2. 负载因子是可以修改的，也可以大于1，但是建议不要轻易修改。
3. HashMap是线程不安全的，不要在并发的环境中同时操作HashMap，建议使用ConcurrentHashMap。
4. JDK1.8引入红黑树很大程度优化了HashMap的性能。

阅读源码是一件十分耗费精力的事情，但从中你可以领悟到JDK作者的巧妙思路，在源码层面去理解为什么HashMap是线程不安全的，HashMap的扩容机制等等，而不是仅仅停留在会用HashMap这个容器的表面理解上。