高效编程之hashmap你不看就会忘记的知识点
以前菜得不能看的时候看Java的招聘要求：Java基础扎实，熟悉常用集合类，多线程，IO，网络编程，经常会疑惑，集合类不就ArrayList，HashMap会用，熟悉下API不就好了么，知道得越多才会发觉不知道的还有好多！
本文使用的源码是jdk1.7的源码，hashmap每个版本都发生了改变，源码都不同，但原理都是一样的，可以参考一下；
读下文前可以先思考以下这几个问题，带着问题去阅读，收获更大；
1、平时我为什么要用hashmap？key和value是以什么样的形式存在的？
2、我了解hashmap的内部结构和实现原理吗？
3、hashmap构造方法的参数有哪些，有什么用？
4、用hashmap的时候需不需要给他一个初始化大小？如果要该怎么定义？
5、不起眼的hashcode和equals方法为什么在hashmap中至关重要？
6、什么是哈希冲突？发生哈希冲突好还是不好？不好该怎么解决？
7、hashmap有什么缺点？它跟hashtable有什么性能区别？
从下面的两张图可以看到，hashmap是由数组和链表组成的；
数组：数组存储区间是连续的，占用内存严重，故空间复杂的很大。但数组的二分查找时间复杂度小，为O(1)；数组的特点是：寻址容易，插入和删除困难；
链表：链表存储区间离散，占用内存比较宽松，故空间复杂度很小，但时间复杂度很大，达O（N）。链表的特点是：寻址困难，插入和删除容易；
哈希表：这时候该引出哈希表了，哈希表寻址容易，插入删除也容易，同事还满足了数据的查找方便，同时不占用太多的内容空间，使用也十分方便！简直牛逼啊~
先盗两张图...因为我不会画...
image.png
hashmap是基于Map接口实现、允许null键/值、非同步这个大家应该都是知道的... 这个时候应该对hashmap有个感性的认识了
那我们从API里面来看看hashmap的构造方法，初始一下 initialCapacity 和 loadFactor 两个名词：
HashMap() 构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空HashMap。
HashMap(int initialCapacity) 构造一个带指定初始容量和默认加载因子 (0.75) 的空HashMap。
HashMap(int initialCapacity, float loadFactor) 构造一个带指定初始容量和加载因子的空HashMap。
initialCapacity是哈希表的数组的初始大小，loadFactor是加载因子；
HashMap的默认大小是16，那么他的数组长度就是0-15；默认加载因子是0.75；
为什么是16呢不是其他的数字呢？为什么默认的加载因子是0.75呢？ 留个悬念哈~后面会提到的！
我们可以看到hashmap里面存放的是一个一个的Entry对象，（下文中的entry/entry对象即为此处的Entry对象）
我们看看看看hashmap是如何定义的Entry对象；
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
上面这是Entry对象的部分代码；
final K key ：表示key是不能改变的 final关键字！
value：这没啥好说的；
Entry<k,v> next 指向下一个节点；
int hash：这个hash 是一个散列码是这样得到的：int hash = hash(key.hashcode（）)；下文会有详细讲解~
image.png
重点部分来了！
HashMap的put方法：
put方法大致的思路是：
1、对key的hashCode()做hash，然后再计算存到数组里的下标;
2、如果没发生冲突直接放到数组里；
3、如果冲突了，以链表的形式存在对应的数组[ i ]中 ；
4、如果冲突导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树；
5、如果节点已经存在就替换old value(保证key的唯一性)
6、如果数组满了(超过load factor*current capacity)，就要resize（扩容）。`
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
这是jdk1.7的源码，1.8只是多了一个新特性，当链表的长度>7的时候，链表转换为红黑树提高查询的效率；
代码有注释，我这里再分析一次；首先通过key.hashcode()出哈希码，哈希码拿去做hash运算算出一个散列值，散列值（hash）跟数组的长度做indexFor运算，就得到了一个entry对象要存到数组的下标，这里有一个要点！ 就是这个hash运算的算法设计，因为就算你拿不同的key去调用hashcode方法得到不同的值拿去做hash运算都会得到一个相同的值，然后把相同的散列值拿去做indexFor运算就会得到相同的 i ，这就发生了哈希表的冲突~~ 发生冲突了怎么办呢？
这里解释源码里的 if 中的判断，因为hash(散列值)是会算出重复的（冲突嘛~），如果这个Entry对象的hash（散列值）和你拿进来的key算的散列值（hash=hash(key)）是一样的并且key也相等（==），那么你放进来的这个entry对象是同一个对象，hashmap允许你的key为空，但是key不能相同，所以新进来的会覆盖旧的；或者key.equals(k)，如果这两个对象通过hashmap重写的equals方法判断是一样的，那也说明是同一个entry对象嘛！怎么办？ 老办法，新的覆盖旧的！其他发生冲突的情况就把新加入的entry对象放到对应数组下标位置的表头，早进来的entry对象后移一个位置，这就形成了一个链表~~!
好的，上面说的挺啰嗦的，下面来个1.8版本的总结，1.8跟1.7差不多~，1.8只是多了一个新特性，当链表的长度>=8的时候，链表转换为红黑树提高查询的效率；
1.8 链表转红黑树的源码
static final int TREEIFY_THRESHOLD = 8;
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
扩容的源码：
添加entry对象的时候如果会时刻判断需不需要扩容数组
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);
}
threshold是一个域值：是由现在的数组容量加载因子；比如初始容量是16，加载因子是0.75；那么threshold=160.75=12； 当数组.size达到12的时候就会扩容了，
会把数组的大小从16扩容到32，那么这时的情况就是，哈希表的数组有第12个元素时，数组就会扩容到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];
boolean oldAltHashing = useAltHashing;
useAltHashing |= sun.misc.VM.isBooted() &&
(newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean rehash = oldAltHashing ^ useAltHashing;
transfer(newTable, rehash);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
new Capacity 就是那个两倍的数组对象，（上面的2*table.length）；
transf（newTable,rehash）这个方法是把原来那个未扩容前数组里的所有entry对象复制到现在这个新数组中来；
此时的域值 threshold 的大小就是新的数组大小 * 0.75 ；
说完put，说get~
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
//先定位到数组元素，再遍历该元素处的链表
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;
}
分析完put，get就容易理解多了~
key==null，这个情况不用讲了吧~
还是先算出散列码的值，然后通过散列码定位到数组（table）下标，也就是常说的通过key就可以拿到value，hashmap底层都是通过key拿到entry对象，然后直接从entry对象里拿到value的；
接着说：如果通过key找到了entry对象，进入if判断，第一种情况：如果entry对象的散列码和 传进来key的散列码是相等（都是int嘛，直接判断是否相等）并且entry对象的key和你传进来的key如果也相等那么就认为是你的key跟你要找的key是同一个，那么就直接return你要的value； 哦对了，这个Object k，是为了去接收entry对象的key（然后赋值给object的k）然后才好和你传进来的key做比较，因为人家不知道你传进来的是什么类型的嘛，用object比就不会有类型转换的错误；
第二种情况：如果e.hash == hash 然后你传进来的key和entry对象的key连重写后的equals后都一样，那肯定就是同一个key了嘛；
不知道我这个菜鸟分析得怎么样，不过可以通过以下几个问题来加深对HashMap的理解；
1. 什么时候会使用HashMap？他有什么特点？
是基于Map接口的实现，存储键值对时，它可以接收null的键值，是非同步的线程不安全，HashMap存储着Entry(hash, key, value, next)对象。
2. 你知道HashMap的工作原理吗？
通过hash的方法，通过put和get存储和获取对象。存储对象时，我们将key传给put方法时，它调用hashCode计算hash从而得到储存的数组下标位置，进一步存储，HashMap会根据当前数组的占用情况自动调整容量(超过域值时则resize为原来的2倍)。获取对象时，我们将key传给get方法，它调用hashCode计算hash从而得到数组下标位置，并进一步调用equals()方法确定键值对。如果发生冲突的时候，Hashmap通过链表将产生碰撞冲突的元素组织起来，在Java 8中，如果一个数组中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高速度。
3.为什么要重写hashcode和equals方法？
1、因为要得到散列码（hash）的时候要通过key.hashcode（）去得到key的哈希码才可以做hash运算；不论是put和get方法，都要使用equals方法，equals方法是object的一个方法，直接调用是比较内存（object.equals源码是用==做比较）；
2、Java约定在用集合类中要重写hashcode和equals方法； Effective java 这本书第二章有详细的解释为什么要定义这样的公约，感兴趣的可以去看看；
4、 为什么HashMap的初始大小是16？为什么默认的加载因子是0.75？HashMap的大小超过了加载因子定义的容量，怎么办？
16是2的4次方，hashmap在put的时候会发生冲突，hashmap发生冲突是不可避免的，也是我们想要的，但是我们不想hashmap傻不拉几的发生冲突，因为最坏的情况，hashmap所有的冲突都发生在同一个数组下标的话，这个位置的链表过长，而其他数组位置确实空的，这样又hashmap还扩容不了，链表的查询效率可想而知，这样的话hashmap还有那么牛逼吗？把数组的长度设计成为2的n次方，加载因子设计为0.75，会极大的优化冲突，使每个数组的链表都差不多长（也不一定，概率问题）；
至于为什么？ 这是数据结构相关的东西，当时是数学家设计的啊，你问我怎么知道的？ 不记得什么时候看了篇论文还是博客，上面是这样说的我真的印象很深的记得我看到过，如果你不信也没办法 反正是有这么回事~
如果超过了负载因子，则会重新resize一个原来长度两倍的HashMap。
5、如果两个键的hashcode相同，你如何获取对象的值？
获取对象的值，那么就是get方法咯，两个key的hashcode相同说明 散列码（hash）相同，
如果散列码都相同了，那么就会调用key.equals（）去判断在该散列码得到的这个数组下标的链表里的entry对象是否有相同的对象；
如果有，那么好，你直接拿这个entry对象的值即可；
6、用hashmap的时候需不需要给他一个初始化大小？如果要该怎么定义？
此问题是博主自己想出来的，答案也是博主自己思考的一个结果，不一定对，提供一个思路！如果你有更好的回答，可以留言给我一起探讨，谢谢啦~
最好是需要的，因为我们知道hashmap的数组长度超过了他的域值会扩容，扩容的时候会把hashmap中所有的entry对象再计算一次他们在新数组中的下标；可以想象一下，如果一个hashmap里有10万个entry对象了，如果要扩容，这10万个entry对象的位置都要发生变化，这会有多影响系统性能？不优化一下吗？ 如何定义这个我也回答不了...因为我们只能初始化数组的大小，并不会知道每个数组元素的链表会有多长，我看同事他们创建hashmap的时候好像都没有给参数，那么如果这10万条数据放到一个大小为16的hashmap里，如果不扩容的话10万条数据只放在数组的11个元素中，那平均每个链表长度有接近1W，肯定不合理吗，链表的查询速度那么慢，所以我们判断必定会扩容，好！我们知道会扩容，但不知道会扩容几次啊，这里就是这个问题难的地方了，因为我们无法知道hashmap会扩容多少次，我们能做的就是减少他扩容的次数，同时又不让hashmap占太多内存~ 那我们就大胆的预测吧，比如有10万条数据，我觉得至少hashmap数组长度应该给1W吧，这样我们就可以把hashmap的初始大小定义为2的14次方 16384，这样数组的长度我们就定义了1.6W，就算用了1W个，也不会扩容，也没浪费更多的资源；如果你觉得10万条数据可能用不到1W个数组这么长，那你就把hashmap的初始大小定义为2的13次方，或者2的12次方；我们开始就定义一个大小总比我们不定义好（毕竟默认只有16）对吧？
7、我们可以用自定义的对象作为hashmap的key吗？如果可以，你会自定义对象当做key吗？如果不行说明原因。
可以使用自定义的对象作为hashmap的key，只要重写hashcode和equals方法就可以了，原因见第三个问题的回答；
但我一般不会把自定义对象作为key，因为有Integer跟string给我用，没必要使用自定义对象了，复杂，麻烦~
8、那你平时使用hashmap的时候一般用什么当做key，为什么？
Integer跟string呀，因为用他们用起来简单啊，Entry对象的四个属性中key是被final关键字修饰的，而Integer和string都是不可变的，直接使用Integer和string岂不美哉
9、hashmap并不能保证线程安全，如果要保证线程安全怎么办？
hashtable能保证线程安全，但有一种更高效的方式就是使用CocurrentHashMap来保证线程安全，同时效率又高；
hashtable是锁住整个数组，一次只能有一个线程去hashtable里面拿，而CocurrentHashMap是只锁数组[ i ] ，所以CocurrentHashMap的效率会比hashtable快很多，又比hashmap安全性要高，实在是居家旅行之首选~
10、那你还知道什么类似hashmap的东西吗？
有个安卓的大牛告诉我有 SarseArray , 安卓内部特有的一个API，因为hashmap用entry来保存key和value，这里entry涉及自动装箱和拆箱，其实挺占内存的；在key为Integer的场景可以使用SarseArray；（后半段来自搜索的解释）假设现在有这样的情况，我们定义了一个长度为100的数组，虚拟机为我们开辟了100个单位的内存空间，但是我们只使用了很少（假设是5个）的一些单元，这样就造成了内存空间的浪费。而 SparseArray 是一个优化的数组，它的 key 是 Integer 类型而不是其他类型，是因为这个数组是按照 key 值的大小来排序的。按照 key 值大小排序的好处是查找的时候，可以使用二分查找，而不是蛮力的遍历整个数组。这也是为什么 SparseArray 适合替换 HashMap<Integer,<E>>，而不是任何 HashMap 的原因了。在这种情况下，原本需要100个单位内存空间而 SparseArray 只占用了5个单位的内存（实际比5个单位要大一些，因为还有一些逻辑控制的内存消耗）。key 值被当成了数组下标的功能来使用了。 安卓用SarseArray 很大一部分原因就是因为 SarseArray 比较节约内存；
