java中HashMap底层实现原理和源码解析
java中HashMap底层实现原理
散列表（Hash table，也叫哈希表），是依据关键码值(Key value)而直接进行訪问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来訪问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。比如我们要存储八十八个数据,我们为他申请了100个元素的地址空间,80/100=0.88,这个数字叫做负载因子.我们之所以这样做是为了通过牺牲空间来换取时间,达到"高速存储"的目的.我们基于一种结果尽可能随机平均分布的固定函数H为每一个元素安排存储位置，这样就能够避免遍历性质的线性搜索，以达到高速存取。可是因为此随机性，也必定导致一个问题就是冲突。所谓冲突，即两个元素通过散列函数H得到的地址同样，那么这两个元素称为“同义词”。
解决冲突是一个复杂问题。冲突主要取决于：
（1）散列函数，一个好的散列函数的值应尽可能平均分布。
（2）处理冲突方法。
（3）负载因子的大小。太大不一定就好，并且浪费空间严重，负载因子和散列函数是联动的。
解决冲突的办法：
（1）线性探查法：冲突后，线性向前试探，找到近期的一个空位置。缺点是会出现堆积现象。存取时，可能不是同义词的词也位于探查序列，影响效率。
（2）双散列函数法：在位置d冲突后，再次使用还有一个散列函数产生一个与散列表桶容量m互质的数c，依次试探(d+n*c)%m，使探查序列跳跃式分布。
影响产生冲突多少有下面三个因素：
1.散列函数是否均匀；
2.处理冲突的方法；
3.散列表的装填因子。
散列表的装填因子定义为：α= 填入表中的元素个数/散列表的长度
α是散列表装满程度的标志因子。因为表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表中的元素较少，产生冲突的可能性就越小。
HashMap数组(JDK8以前使用拉链法,JDK8以后使用红黑树)
在Java编程语言中，最基本的结构就是两种，一种是数组，一种是模拟指针(引用),所有的数据结构都可以用这两个基本结构构造，HashMap也一样。当程序试图将多个key-value 放入HashMap中时，以如下代码片段为例：
HashMap
m.put("a", "rrr1");
m.put("b", "tt9");
m.put("c", "tt8");
m.put("d", "g7");
m.put("e", "d6");
HashMap采用一种所谓的“Hash 算法”来决定每个元素的存储位置。当程序执行map.put(String,Obect)方法时，系统将调用String的hashCode()方法得到其hashCode 值——每个Java对象都有hashCode()方法，都可通过该方法获得它的hashCode 值。得到这个对象的hashCode 值之后，系统会根据该hashCode 值来决定该元素的存储位置。源码如下:
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry
Object k;
//判断当前确定的索引位置是否存在相同hashcode和相同key的元素，如果存在相同的hashcode和相同的key的元素，那么新值覆盖原来的旧值，并返回旧值。
//如果存在相同的hashcode，那么他们确定的索引位置就相同，这时判断他们的key 是否相同，如果不相同，这时就是产生了hash冲突。
//Hash冲突后，那么HashMap的单个bucket里存储的不是一个 Entry，而是一个 Entry 链。
//系统只能必须按顺序遍历每个 Entry，直到找到想搜索的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端（该 Entry 是最早放入该 bucket 中），
//那系统必须循环到最后才能找到该元素。
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
上面程序中用到了一个重要的内部接口：Map.Entry，每个Map.Entry其实就是一个key-value对。从上面程序中可以看出：当系统决定存储HashMap中的key-value对时，完全没有考虑Entry中的value，仅仅只是根据key来计算并决定每个Entry的存储位置。
这也说明了前面的结论：我们完全可以把Map集合中的value当成key 的附属，当系统决定了key 的存储位置之后，value 随之保存在那里即可.HashMap程序经过我改造，我故意的构造出了hash冲突现象，因为HashMap的初始大小16,但是我在hashmap里面放了超过16个元素，并且我屏蔽了它的resize()方法。不让它去扩容。这时HashMap的底层数组Entry[] table结构如下:
Hashmap里面的bucket出现了单链表的形式，散列表要解决的一个问题就是散列值的冲突问题，通常是两种方法：链表法和开放地址法。链表法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位；开放地址法是通过一个探测算法，当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位。java.util.HashMap采用的链表法的方式，链表是单向链表。形成单链表的核心代码如下：
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry
table[bucketIndex] = new Entry
if (size++ >= threshold)
resize(2 * table.length);
上面方法的代码很简单，但其中包含了一个设计：系统总是将新添加的Entry对象放入table数组的bucketIndex索引处——如果bucketIndex索引处已经有了一个Entry对象，那新添加的Entry对象指向原有的Entry 对象（产生一个Entry 链），如果bucketIndex 索引处没有Entry 对象，也就是上面程序代码的e 变量是null，也就是新放入的Entry 对象指向null，也就是没有产生Entry 链。
HashMap里面没有出现hash冲突时，没有形成单链表时，hashmap查找元素很快,get()方法能够直接定位到元素，但是出现单链表后，单个bucket 里存储的不是一个Entry，而是一个Entry链，系统只能必须按顺序遍历每个Entry，直到找到想搜索的Entry为止——如果恰好要搜索的Entry位于该Entry链的最末端（该Entry是最早放入该bucket 中），那系统必须循环到最后才能找到该元素。
当创建HashMap 时，有一个默认的负载因子（load factor），其默认值为0.75，这是时间和空间成本上一种折衷：增大负载因子可以减少Hash表（就是那个Entry数组）所占用的内存空间，但会增加查询数据的时间开销，而查询是最频繁的的操作（HashMap的get() 与put() 方法都要用到查询）；减小负载因子会提高数据查询的性能，但会增加Hash 表所占用的内存空间。
三、HashMap源码分析
1、关键属性
先看看HashMap类中的一些关键属性：
transient Entry[] table;//存储元素的实体数组
transient int size;//存放元素的个数
int threshold; //临界值当实际大小超过临界值时，会进行扩容threshold = 加载因子*容量
final float loadFactor; //加载因子
transient int modCount;//被修改的次数
2、构造方法
下面看看HashMap的几个构造方法：
public HashMap(int initialCapacity, float loadFactor) {
//确保数字合法
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// Find a power of 2 >= initialCapacity
int capacity = 1; //初始容量
while (capacity < initialCapacity) //确保容量为2的n次幂，使capacity为大于initialCapacity的最小的2的n次幂
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int)(capacity*loadFactor);
table = new Entry[capacity];
init();
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
我们可以看到在构造HashMap的时候如果我们指定了加载因子和初始容量的话就调用第一个构造方法，否则的话就是用默认的。默认初始容量为16，默认加载因子为0.75。我们可以看到上面代码中13-15行，这段代码的作用是确保容量为2的n次幂，使capacity 为大于initialCapacity的最小的2的n次幂，至于为什么要把容量设置为2的n次幂，我们等下再看。
重点分析下HashMap中用的最多的两个方法put和get
3、存储数据
下面看看HashMap存储数据的过程是怎样的，首先看看HashMap的put方法：
public V put(K key, V value) {
//若“key为null”，则将该键值对添加到table[0]中。
if(key == null)
return putForNullKey(value);
//若“key不为null”，则计算该key的哈希值，然后将其添加到该哈希值对应的链表中。
int hash = hash(key.hashCode());
//搜索指定hash值在对应table中的索引
int i = indexFor(hash, table.length);
//循环遍历Entry数组,若“该key”对应的键值对已经存在，则用新的value取代旧的value。然后退出！
for (Entry
Object k;
if(e.hash == hash && ((k = e.key) == key || key.equals(k))) { //如果key相同则覆盖并返回旧值
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
//修改次数+1
modCount++;
//将key-value添加到table[i]处
addEntry(hash, key, value, i);
return null;
}
上面程序中用到了一个重要的内部接口：Map.Entry，每个Map.Entry其实就是一个key-value对。从上面程序中可以看出：当系统决定存储HashMap中的key-value对时，完全没有考虑Entry中的value，仅仅只是根据key来计算并决定每个Entry 的存储位置。这也说明了前面的结论：我们完全可以把Map集合中的value当成key的附属，当系统决定了key的存储位置之后，value随之保存在那里即可。
我们慢慢的来分析这个函数，第2和3行的作用就是处理key值为null的情况，我们看看putForNullKey(value)方法：
注意：如果key为null的话，hash值为0，对象存储在数组中索引为0的位置。即table[0].
我们再回去看看put方法中第4行，它是通过key的hashCode值计算hash码，下面是计算hash码的函数：
//计算hash值的方法通过键的hashCode来计算
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);
}
得到hash码之后就会通过hash码去计算出应该存储在数组中的索引，计算索引的函数
如下：
static int indexFor(int h, int length) { //根据hash值和数组长度算出索引值return h & (length-1); //这里不能随便算取，用hash&(length-1)是有原因的，这样可以确保算出来的索引是在数组大小范围内，不会超出
}
这个我们要重点说下，我们一般对哈希表的散列很自然地会想到hash值对length取模（即除法散列法），Hashtable中也是这样实现的，这种方法基本能保证元素在哈希表中散列的比较均匀，但取模会用到除法运算，效率很低，HashMap中则通过h&(length-1)的方法来代替取模，同样实现了均匀的散列，但效率要高很多，这也是HashMap对Hashtable的一个改进。
接下来，我们分析下为什么哈希表的容量一定要是2的整数次幂。首先，length为2的整数次幂的话，h&(length-1)就相当于对length取模，这样便保证了散列的均匀，同时也提升了效率；其次，length为2的整数次幂的话，为偶数，这样length-1为奇数，奇数的最后一位是1，这样便保证了h&(length-1)的最后一位可能为0，也可能为1（这取决于h 的值），即与后的结果可能为偶数，也可能为奇数，这样便可以保证散列的均匀性，而如果length为奇数的话，很明显length-1为偶数，它的最后一位是0，这样h&(length-1)的最后一位肯定为0，即只能为偶数，这样任何hash值都只会被散列到数组的偶数下标位置上，这便浪费了近一半的空间，因此，length取2的整数次幂，是为了使不同hash值发生碰撞的概率较小，这样就能使元素在哈希表中均匀地散列。
根据上面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()方法的说明。
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry
table[bucketIndex] = new Entry<>(hash, key, value, e);
if (size++ >= threshold) //如果大于临界值就扩容
resize(2 * table.length); //以2的倍数扩容
}
参数bucketIndex就是indexFor函数计算出来的索引值，第2行代码是取得数组中索引为bucketIndex的Entry对象，第3行就是用hash、key、value构建一个新的Entry对象放到索引为bucketIndex的位置，并且将该位置原先的对象设置为新对象的next构成链表。
第4行和第5行就是判断put后size是否达到了临界值threshold，如果达到了临界值就要进行扩容，HashMap扩容是扩为原来的两倍。
4、调整大小
resize()方法如下：
重新调整HashMap的大小，newCapacity是调整后的单位
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里面
table = newTable; //再将newTable赋值给table
threshold = (int)(newCapacity * loadFactor);//重新计算临界值
}
新建了一个HashMap的底层数组，上面代码中第10行为调用transfer方法，将HashMap 的全部元素添加到新的HashMap中,并重新计算元素在新的数组中的索引位置。
当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，这是一个常用的操作，而在HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。
那么HashMap什么时候进行扩容呢？当HashMap中的元素个数超过数组大小*loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中元素个数超过16*0.75=12的时候，就把数组的大小扩展为2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，扩容是需要进行数组复制的，复制数组是非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。
5、数据读取
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
有了上面存储时的hash算法作为基础，理解起来这段代码就很容易了。从上面的源代码中可以看出：从HashMap中get元素时，首先计算key的hashCode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。
6、HashMap的性能参数：
HashMap 包含如下几个构造器：
HashMap()：构建一个初始容量为16，负载因子为0.75 的HashMap。
HashMap(int initialCapacity)：构建一个初始容量为initialCapacity，负载因子为0.75的HashMap。
HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的负载因子创建一个HashMap。
HashMap的基础构造器HashMap(int initialCapacity, float loadFactor)带有两个参数，它们是初始容量initialCapacity和加载因子loadFactor。
initialCapacity：HashMap的最大容量，即为底层数组的长度。
loadFactor：负载因子loadFactor定义为：散列表的实际元素数目(n)/ 散列表的容量(m)。
负载因子衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。对于使用链表法的散列表来说，查找一个元素的平均时间是O(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。HashMap的实现中，通过threshold 字段来判断HashMap的最大容量：
threshold = (int)(capacity * loadFactor);
结合负载因子的定义公式可知，threshold就是在此loadFactor和capacity对应下允许的最大元素数目，超过这个数目就重新resize，以降低实际的负载因子。默认的的负载因子0.75是对空间和时间效率的一个平衡选择。当容量超出此最大容量时，resize后的HashMap 容量是容量的两倍。JDK8新增的红黑树:
HashMap 在JDK 1.8 中新增的操作：桶的树形化treeifyBin()
在Java 8中，如果一个桶中的元素个数超过TREEIFY_THRESHOLD(默认是8 )，就使用红黑树来替换链表，从而提高速度。这个替换的方法叫treeifyBin() 即树形化。
//将桶内所有的链表节点替换成红黑树节点
final void treeifyBin(Node
int n, index; Node
//如果当前哈希表为空，或者哈希表中元素的个数小于进行树形化的阈值(默认为64)，就去新建/扩容
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
//如果哈希表中的元素个数超过了树形化阈值，进行树形化
// e 是哈希表中指定位置桶里的链表节点，从第一个开始
TreeNode
do {
//新建一个树形节点，内容和当前链表节点e 一致
TreeNode
if (tl == null) //确定树头节点
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
//让桶的第一个元素指向新建的红黑树头结点，以后这个桶里的元素就是红黑树而不是链表了
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
TreeNode
return new TreeNode<>(p.hash, p.key, p.value, next);
}
北大青鸟推荐：Java精选笔试题(含答案解析)
北大青鸟推荐：Java精选笔试题（含答案解析）如果你是计算机专业出生，但是还没有找到工作的话，你就得补补技术了，一些关于面试、笔试的题要多刷一刷。有可能你知道答案，但是由于语言组织能力有所欠缺，所以面试官的印象不是很好，下面分享一些Java精选的鄙视题，希望对面试这者有帮助。 1，volatile关键字是否能保证线程安全？（） 答案：否 volatile关键字用在多线程同步中，可保证读取的可见性，JVM只是保证从主内存加载到线程工作内存的值是最新的读取值，而非cache中。但多个线程对volatile的写操作，无法保证线程安全。 假如线程1，线程2 在进行read,load 操作中，发现主内存中count的值都是5，那么都会加载这个最新的值，在线程1对count进行修改之后，会write到主内存中，主内存中的count变量就会变为6；线程2由于已经进行read,load操作，在进行运算之后，也会更新主内存count的变量值为6；导致两个线程及时volatile关键字修改之后，还是会存在并发的情况。 2，下面哪个流类属于面向字符的输入流( ) A、BufferedWriter B、FileInputStream C、ObjectInputStream D、InputStreamReader 答案：D Java的IO操作中有面向字节(Byte)和面向字符(Character)两种方式。
面向字节的操作为以8位为单位对二进制的数据进行操作，对数据不进行转换，这些类都是InputStream和OutputStream的子类。 面向字符的操作为以字符为单位对数据进行操作，在读的时候将二进制数据转为字符，在写的时候将字符转为二进制数据，这些类都是Reader和Writer的子类。 3，Java能不能不通过构造函数创建对象（） A、能 B、不能 答案：A Java创建对象的几种方式： (1) 用new语句创建对象，这是最常见的创建对象的方法。 (2) 运用反射手段,调用https://www.wendangku.net/doc/bd3535302.html,ng.Class或者https://www.wendangku.net/doc/bd3535302.html,ng.reflect.Constructor类的newInstance()实例方法。 (3) 调用对象的clone()方法。 (4) 运用反序列化手段，调用java.io.ObjectInputStream对象的readObject()方法。 (1)和(2)都会明确的显式的调用构造函数；(3)是在内存上对已有对象的影印，所以不会调用构造函数；(4)是从文件中还原类的对象，也不会调用构造函数。 4，下列哪个叙述是正确的（） A.子类继承父类的构造方法。 B.abstract类的子类必须是非abstract类。 C.子类继承的方法只能操作子类继承和隐藏的成员变量。 D.子类重写或新增的方法也能直接操作被子类隐藏的成员变量。 答案：C 子类是不继承父类的构造方法的，而是必须调用其父类的构造方法。
Java API 试题
永隆 JAVA笔试题 一、选择题 1、关于Java 类的加载过程，下面哪些描述是正确的（） A、在 Java 中，有四种类型的类加载器：BootStrapClassLoader、ExtClassLoader、AppClassLoader 以及用户自定义的ClassLoader。//Extension ClassLoader, System ClassLoader+用户自定义的classloader B、使用 new 关键字创建类实例时，其实就显示地包含了类的加载过程 C、在 Java 中，类的实例化流程分为两个部分：类的加载和类的实例化。类的加载又分为显式加载和隐式加载。 D、Class.forName 来加载类时，是通过 ExtClassLoader进行加载的。 //system classLoader 加载 2、关于HashMap的实现机制，下面哪些描述是正确的（） A、HashMap中key-value 当成一个整体进行处理，系统总是根据数组的坐标来获得key-value 的存储位置。//没有存储顺序，无下标之说！ B、HashMap基于哈希表的 Map 接口的实现，允许使用 null 值和 null 键。 C、如果HashMap中，如果Key的hash相同的话，HashMap将会出错。//会替换相应的value D、HashMap每次容量的扩增都是以2的倍数来增加。//大约获得2倍的桶数！ 3、下面的代码执行输出正确的是（） 1. public class test( 2. public int aMethod()[ 3. static int i=0; 4. i++; 5. return I; 6. ) 7. public static void main (String args[]){ 8. test test = new test(); 9. test.aMethod(); 10.int j = test.aMethod(); 11.System.out.printIn(j); 12.] 13.} A. 编译错误 B. 编译成功，打印出是“0” C. 编译成功，打印出是“1” D. 编译成功，打印出是“2” A 4、如何获取下面表单 select