简单理解HashMap
- 什么时候会使用HashMap？他有什么特点？
- 你知道HashMap的工作原理吗？
- 你知道get和put的原理吗？equals()和hashCode()的都有什么作用？
- 你知道hash的实现吗？为什么要这样实现？
- 如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？
说明：HashMap的源码每个版本是有一些细微的差别，但是大体上都差不多，下面我整理的是jdk1.6的。有一个比较明显的区别是在1.8如果发生了碰撞的时候在一定值之前使用链表进行表示，在超过这个值的时候用的是红黑树。
HashMap是实现Map接口的类，是非线程安全的。允许null键，和null值。不保证映射的顺序
-
结构示意图：在java里，所有的数据结构基本上都是由数组，引用来组成的。HashMap实际上是由 一个数组链表组成的。如图所示：
HashMap<String, Integer> map = new HashMap<String, Integer>();
map.put("语文", 1);
map.put("数学", 2);
map.put("英语", 3);
map.put("历史", 4);
map.put("政治", 5);
map.put("地理", 6);
map.put("生物", 7);
map.put("化学", 8);
- HashMap中的数组里的类型是Entry的（java8里换了个，叫Node：节点，它是用树这种数据结构）
- Entry的源码如下，next的就是向下的引用（指针），这个会构成链表
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient Entry[] table;
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
……
}
HashMap的put方法：
public V put(K key, V value) {
// 存了null的key
if (key == null)
return putForNullKey(value);
// 根据key的keyCode重新计算hash值。
int hash = hash(key.hashCode());
// 搜索指定hash值在对应table中的索引。
int i = indexFor(hash, table.length);
// 如果 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个元素。
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 假如新加的key值相同，那么则覆盖
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// 如果i索引处的Entry为null，表明此处还没有Entry。
modCount++;
// 将key、value添加到i索引处。
addEntry(hash, key, value, i);
return null;
}
- 假如table[bucketIndex]上已经存值了，那么则会把新加的放在链表的第一个，这个Entry的next则会指向之前的那个值。
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);
}
Entry (int h , K k, V v , Entry <K,V> n ) {
value = v ;
next = n ;
key = k ;
hash = h ;
}
hash方法和indexFor方法
- jdk 1.6
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);
}
/**
* Returns index for hash code h.
*/
static int indexFor(int h , int length) {
return h & (length-1);
}
- jdk 1.8
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
(n - 1) & hash
- put方法的总结：
根据上面 put 方法的源代码可以看出:
- 当程序试图将一个key-value对放入HashMap中时，程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置
- 如果两个 Entry 的 key 的 hashCode() 返回值相同，那它们的存储位置相同。
- 如果这两个 Entry 的 key 通过 equals 比较返回 true，新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value，但key不会覆盖。
- 如果这两个 Entry 的 key 通过 equals 比较返回 false，新添加的 Entry 将与集合中原有 Entry 形成 Entry 链，而且新添加的 Entry 位于 Entry 链的头部——具体说明继续看 addEntry() 方法的说明。
get方法
理解了上面的put方法，自然get方法也就很好理解了
public V get( Object key ) {
if (key == null)
return getForNullKey(); //取出键值是null的value
//计算优化过的hash值
inthash= hash(key.hashCode());
//计算了key值所在的位置，然后遍历这个位置的链表，直到找到
for(Entry<K,V>e=table[indexFor(hash,table.length)];
e != null;
e = e .next ) {
Object k;
if (e .hash == hash && (( k = e. key) == key || key. equals( k)))
return e. value;
}
return null;
}
resize方法：
当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，这是一个常用的操作，而在HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。
当HashMap中的元素个数超过数组大小loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中元素个数超过160.75=12的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，
- 代码如下：
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);
}
- 所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能
前方高能预警！
让我们来看看jdk1.8中是怎么实现的吧：
Initializes or doubles table size. If null, allocates in accord with initial capacity target held in field threshold. Otherwise, because we are using power-of-two expansion, the elements from each bin must either stay at same index, or move with a power of two offset in the new table.
大致意思就是说，当超过限制的时候会resize，然而又因为我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。
-
怎么理解呢？例如我们从16扩展为32时，具体的变化如下所示：
- 因此元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：
- 因此，我们在扩充HashMap的时候，不需要重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。可以看看下图为16扩充为32的resize示意图：
这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。
思考？为什么所HashMap不是线程安全的：
此实现不是同步的。如果多个线程同时访问一个哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须 保持外部同步。（结构上的修改是指添加或删除一个或多个映射关系的任何操作；仅改变与实例已经包含的键关联的值不是结构上的修改。）这一般通过对自然封装该映射的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedMap 方法来“包装”该映射。最好在创建时完成这一操作，以防止对映射进行意外的非同步访问，如下所示： Map m = Collections.synchronizedMap(new HashMap(...));
自己的理解：当有多个线程同时要put和remove的时候，假如都获取到了HashMap的头结点，那么这时多个线程就会同时操作，导致先操作的被后操作的覆盖了。另外就是在addEntry中当加入新的键值对后键值对总数量超过门限值的时候会调用一个resize操作，这时会重新计算hash值,然后知道算出index位置，先计算的会被后计算的覆盖，另外假如一个线程已经计算完毕，另外一个刚开始，就会导致另外的问题。
- 就是没有实现同步...
HashMap有两个参数，
一个是CAPACITY //容量
另外一个是LOAD_FACTOR //比例
这两个参数应该在一个合适的比例范围内，默认的容量是16，默认的比例是0.75。假如容量过大会太占用内存，太小会经常的扩容。比例太大会让难以填满，比例太小也会浪费内存。
- 什么时候会使用HashMap？他有什么特点？
是基于Map接口的实现，存储键值对时，它可以接收null的键值，是非同步的，HashMap存储着Entry(hash, key, value, next)对象。
- 你知道HashMap的工作原理吗？
通过hash的方法，通过put和get存储和获取对象。存储对象时，我们将K/V传给put方法时，它调用hashCode计算hash从而得到bucket位置，进一步存储，HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。获取对象时，我们将K传给get，它调用hashCode计算hash从而得到bucket位置，并进一步调用equals()方法确定键值对。如果发生碰撞的时候，Hashmap通过链表将产生碰撞冲突的元素组织起来，在Java 8中，如果一个bucket中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高速度。
- 你知道get和put的原理吗？equals()和hashCode()的都有什么作用？
通过对key的hashCode()进行hashing，并计算下标( n-1 & hash)，从而获得buckets的位置。如果产生碰撞，则利用key.equals()方法去链表或树中去查找对应的节点
- 你知道hash的实现吗？为什么要这样实现？
在Java 1.8的实现中，是通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在bucket的n比较小的时候，也能保证考虑到高低bit都参与到hash的计算中，同时不会有太大的开销。
- 如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？
如果超过了负载因子(默认0.75)，则会重新resize一个原来长度两倍的HashMap，并且重新调用hash方法。
