public class HashMap<k,v> extends AbstractMap<k,v> implements Map<k,v>, Cloneable, Serializable {
Map并不是继承自Collection接口
. 继承:
AbstractMap<k,v>
抽象类中提供了一些实现的方法，后面的子类中如果没有特殊的实现细节，可以直接使用AbstractMap中的方法。
.实现:
Map<k,v>
Map接口实现图
这里实现的Map接口，java的设计中通常既然继承了AbstractMap，那么就没有必要实现Map接口，所以这里在Stack Overfloooow中解释的意思是为了让阅读者明确知道HapMap来自Map
Cloneable
Cloneable这个接口设计时并没有clone（）方法，所以在我们实现这个接口的时候需要重写clone()方法，
Serializable
表明HashMap对象是可以被序列化的。
设计理念
HashMap是基于hash表（hashtable）实现的，hash表又叫关联数组，所以HashMap的底层是一个数组，一种键值对数据结构，键是不可以重复的，这里说下HashMap键值对的报存过程，key在经过hash函数作用后会生成一个对应值槽的索引，但是在不同的key经过hash函数处理的时候可能会的到相同的索引，因此会产生重复的情况，因此：
. 设计一个好的hash函数可以尽可能的减少冲突的发生，
.其次是解决如果冲突发生后怎么解决这个冲突。
HashMap的特点：
☆ 与HashMap对应的是HashTable，相比较而言，HashTable是线程安全的，HashMap是允许键值都是null的，但是相反的是HashTable中键值都是部允许为null的，
☆HashMap是无序的，并且随着世间的推移可能会出现某一个元素的位置可能会改变 （resize） 意思就是重新计算容量， 这里涉及到HashMap的扩容机制，既然HashMap的底层是一个数组那么可想而知在java中数组的扩容原理：重新建立一个容量更大的数组，把原来的数组copy到新的数组中即可，其实HashMap的扩容机制也是大相径庭，（ps:HashMap 的初始容量为16，一旦需要扩容的时候会扩大到原来的2倍）关于HashMap的扩容机制在下一段落中会详细介绍。
源码解析
构造函数
HashMap在设计之处的时候提供了四个构造函数：
//initialCapcity ：初始化容量；
//laodFactor ：平衡因子；
在代码中可以看见，HashMap对这两个值都是有默认值的设计：初始化容量为16，平衡因子为0.75；至于平衡因子为什么会选择0.75，JDK中说是平衡了时间和空间因素的最好取值。
这里解释下平衡因子这个东西：平衡因子表示Hash表中元素填满的程度，前面说到了每一个key在存入的时候都会经过hash函数生成一个对应的下表，如果说平衡因子越大，也就是hash表的填满程度越大，这样出现hash冲突的可能性就会越大，在做查找的时候就会花费大量的世间。但是相反的是如果平衡因子越小，这样空间的利用率就会降低，出现内存浪费的情况。所以说，楼主觉得JDK说是平衡了 时间和空间的因素的最好取值还是有道理的O^O。
HashMap的构造函数
Hash函数设计
前面一直说到的hash函数，以及一个好的hash函数，可以降低hash冲突的发生，那么HashMap中的hash函数是怎么设计的呢？（这里是JDK1.8的hash函数，每个版本的JDK中的hash函数设计的是不一样的）
HashMap中的hash函数
可以看见代码的直接意思就是：如果传入的key 为null那么直接返回0，如果不是null那么就是返回原hash值和原hash值的无符号右移16位的异或结果，（这里相比较JDK之前的版本hash函数的设计变得简单了很多）。
为什么要这么设计呢？
一个数右移16位，也就是说任何一个小于2的16次方的数向右移16位都会变成0，在异或运中我们知道任何一个数在和0做异或运算的时候都会返回起本身的值（0^1—>1;0^0—>0），那么就很好理解了代码中在做异或运算的右边只有在大于2的16次方的时候才会重新计算hash值。否则都会直接返回原来的hash值。
说了半天好像没说到关于这样设计的好处在哪里。下面说下这样设计的原理：
首先java中int为4个字节也就是2的32次方，这里先看一张图片：
hash函数运算原理图
为了降低hash的冲突在JDK1.8中hash函数的设计中，使用了移位异或运算，原来的hash值和右移16位的hash值在做异或运算（右位移16位，正好是32bit的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性），这样子出现相同的hash值得概率得到了极大的降低。ps：不得不说这种设计的方式是真滴【皮】！！
HashMap.Entry
在JDK1.8中HashMap存放对象的是Node<K,V> 他继承自Map.Entry<K,V>。
Node<K,V>源码图
可以看出来Entry<K,V>实际上实现了一个单向链表的功能。JDK1.8中使用的是Node<K,V>的静态内部类，
说到Entry<K,V>这里有必要说下HashMap的遍历方法。。。。。。。
HashMap的遍历
HashMap的遍历方式有很多种，这里主要说两种方式的遍历：
①，keySet()这种遍历方式是最普遍的使用方式，但是并不是最好的选择，
Map<K,V> map = new hashMap<K,V>();
for(K key : map.keySet()){
sysout("key = " + key + ＂；＂+ "value = " + map.get(key));
}
②，entrySet() 在JDK1.8中这里其实是Map.Entry<K,V>实现了AbstrarctMap<Map.Entry<K,V>>
这种方式也是最快的遍历方式下面会解释这里使用EntrySet遍历为什么是最快的（相比较）
Map<K,V> map = new HashMap<K,V>();
for(Map.Entry<K,V> node : map.entrySet()){
sysout("key = " + node.getKey() + ＂value = ＂ + node.getValue());
}
③，这里顺便说一下在JDK1.8中新添加forEach()用来遍历集合（forEach()并不推荐使用）
Mapmap = new HashMap();
map.put("1", "aa");
map.put("2", "bb");
map.forEach((k,v) -> System.out.println("k =" + k + "value = " + v));
在数据量很大的时候推荐使用EntrySet遍历Map
SS：在使用keySet遍历map的时候其实是遍历了两次，分别遍历了键和值，相比较而言EntrySet使用一次遍历直接获得了Entry（里面包括了key和value），因此推荐使用EntrySet来遍历
get()操作
public V get(Object key){
//单独处理key为null的情况，这里页证实了HashMap中是允许键为null的情况
if (key ==null){
return getForNullKey ();
}
Entry entry = getEntry(key);
return null== entry ?null: entry.getValue();
}
private V getForNullKey(){
if(size ==0) {
return null;
}
//key为null的Entry用于放在table[0]中，但是在table[0]冲突链中的Entry的key不一定为 null
//所以需要遍历冲突链，查找key是否存在
for(Entry e = table[0]; e !=null; e = e.next) {
if(e.key ==null){
returne.value;
}
}
return null;
}
final EntrygetEntry(Object key){
if(size ==0) {
returnnull;
}
int hash = (key ==null) ?0: hash(key);
//首先定位到索引在table中的位置
//然后遍历冲突链，查找key是否存在
for(Entry e = table[indexFor(hash, table.length)];
e !=null;
e = e.next) {
Object k;
if(e.hash == hash &&((k = e.key) == key || (key !=null&& key.equals(k)))){
return e;
}
}
return null;
}
第一篇先到这里，
网友评论