hashMap

hashmap的底层实现

JDK1.8之前HashMap

hash算法优化

JDK1.7的 HashMap 的 hash 方法

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);
			}

JDK 1.8 HashMap 的 hash 方法

static final int hash(Object key) {
			      int h;
			      // key.hashCode()：返回散列值也就是hashcode
			      // ^ ：按位异或
			      // >>>:无符号右移，忽略符号位，空位都以0补齐
			      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

HashMap 的长度为什么是2的幂次方

寻址算法优化

1. 为了能让 HashMap 存取高效，尽量较少碰撞，减少hash冲突，也就是要尽量把数据分配均匀。
Hash 值的范围值-2147483648到2147483647，前后加起来大概40亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。
但问题是一个40亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标。

2. 与运算效率比取模运算效率高
 
这也就解释了 HashMap 的长度为什么是2的幂次方。这个算法应该如何设计呢？我们首先可能会想到采用%取余的操作来实现。
但是，重点来了：取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作，也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方。并且 采用二进制位操作 &，相对于%能够提高运算效率.

hash冲突解决方式

8之前拉链法

所谓 拉链法 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

JDK1.8之后 红黑树

负载因子是0.75的原因

* rarely used.  Ideally, under random hashCodes, the frequency of
     * nodes in bins follows a Poisson distribution
     * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
     * parameter of about 0.5 on average for the default resizing
     * threshold of 0.75, although with a large variance because of
     * resizing granularity. Ignoring variance, the expected
     * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
     * factorial(k)). The first values are:
     *
     * 0:    0.60653066
     * 1:    0.30326533
     * 2:    0.07581633
     * 3:    0.01263606
     * 4:    0.00157952
     * 5:    0.00015795
     * 6:    0.00001316
     * 7:    0.00000094
     * 8:    0.00000006
     * more: less than 1 in ten million

HashMap 和 Hashtable 的区别

1. 线程是否安全： HashMap 是非线程安全的，HashTable 是线程安全的；HashTable 内部的方法基本都经过 synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）；

2. 效率： 因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 基本被淘汰，不要在代码中使用它；

3. 对Null key 和Null value的支持： HashMap 中，null 可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为 null。。但是在 HashTable 中 put 进的键值只要有一个 null，直接抛出 NullPointerException。

4. 初始容量大小和每次扩充容量大小的不同 ： ①创建时如果不指定容量初始值，Hashtable 默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。②创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为2的幂次方大小（HashMap 中的tableSizeFor()方法保证，下面给出了源代码）。也就是说 HashMap 总是使用2的幂作为哈希表的大小,后面会介绍到为什么是2的幂次方。

5. 底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。

HashMap的扩容机制

核心属性

1. transient int size

1. loadFactor

1. int threshold

1. 除了以上这些重要成员变量外，HashMap中还有一个和他们紧密相关的概念：capacity

1. static final int TREEIFY_THRESHOLD = 8;

1. transient Node<K,V>[] table;//hash表

2. static class Node<K,V> implements Map.Entry<K,V>

final int hash;

final K key;

V value;

Node<K,V> next;

扩容时机

1. hashmap的无参初始化

1. size>=阈值=loadFactor* capacity

扩容过程

1. 新建一个长度为原来2倍的数组

2. transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里。

hashmap的线程安全问题

JDK1.8之前的循环死链

如何线程安全的使用HashMap

Hashtable

public synchronized V get(Object key) {
// 省略实现
}
public synchronized V put(K key, V value) {
// 省略实现
}

Collections.synchronizedMap()

ConcurrentHashMap