<h1>HashMap</h1>

<blockquote>
在许多应用中都需要一种动态集合结构，支持INSERT,SEARCH,DELETE字典操作。而hashtable是实现字典操作的一种有效数据结构。散列表是普通数据结构的推广，由于普通数组能够直接寻址，使得能在O(1）中的时间找到数组的任何位置，利用这种思想，我们可以提供一个数组，为每个可能的关键字保留一个位置，以利用直接寻址的优势。
</blockquote>

<h2>工作原理</h2>

HashMap基于hashing原理，我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算hashcode，让后找到bucket位置来储存值对象。当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。HashMap使用链表来解决碰撞问题，当发生碰撞了，对象将会储存在链表的下一个节点中。 HashMap在每个链表节点中储存键值对对象。

<h2>Capacity和LoadFactor</h2>

容量和负载因子

这两个是hashmap构造函数的两个参数，容量Capacity是bucket的大小，LoadFactor 是bucket填满程度的最大比例，如果对迭代性能要求很高就不要把capacity设置过大，也不要把loadFactor设置过小。当bucket中的entries的数目大于capacity*load facotr时就需要调整bucket的大小为当前的两倍。loadfacotor默认值为0.75f，而Capacity的默认值为16。

<h2>put函数</h2>

<ol>
<li>对key的hashCode()做hash，然后计算index</li>
<li>如果没有碰撞存入bucket</li>
<li>碰撞后以链表的形势存在buckets后</li>
<li>如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换为红黑树，TREEIFY_THRESHOLD的默认值为8</li>
<li>如果节点已经存在就替换old value(保证key的唯一性)。</li>
<li>如果bucket满了（超过load factor * current capacity），就要resize</li>
</ol>

<h2>get函数</h2>

<ol>
<li>bucket里的第一个节点，直接命中</li>
<li>如果有冲突，则通过key.equals(k)查找O(logn)；若为链表，则在链表中通过key.equals(k)查找，O(n)。</li>
</ol>

<h2>hash函数</h2>

高16位不变，低16位和高16位做了一个异或。

在Java 8之前的实现中是用链表解决冲突的，在产生碰撞的情况下，进行get时，两步的时间复杂度是O(1)+O(n)。因此，当碰撞很厉害的时候n很大，O(n)的速度显然是影响速度的。

因此在Java 8中，利用红黑树替换链表，这样复杂度就变成了O(1)+O(logn)了，这样在n很大的时候，能够比较理想的解决这个问题，在Java 8：HashMap的性能提升一文中有性能测试的结果。

<h2>resize的实现</h2>

将容量扩充为以前的两倍

使用一个entry存放在hash桶中，如果有多个，不停的next构成链表。在java 1.8后超出8个，就变为红黑树。

HashTable

说完HashMap，我们来说一说HashTable
hashtable和hashmap的几乎一样，只是有几点不同：

<ol>
<li>HashMap几乎可以等价于Hashtable除了HashMap是非synchronized的，并且可以接受null，HashMap可以接收null的key和value，而Hashtable则不行。</li>
<li>hashtable是synchronized的，线程安全，可以多线程共享一个Hashtable，而hashmap在没有同步的时候是不能线程共享的。在Java5中提供了ConcurrentHashMap，是HashTable的替代，比HashTable扩展性更好</li>
<li>HashMap的迭代器是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以当有其他线程改变了HashMap的结构，将会抛出ConcurrentModificationException，但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。</li>
<li>Hashtable是线程安全的。所以在单线程比HashMap要慢，如果不需要同步，只需要单一线程，HashMap的性能要好过Hashtable。</li>
<li>HashMap不能保证随着时间的推移Map中的元素次序是不变的。</li>
</ol>

<h1>ConcurrentHashMap</h1>

上面有提到ConcurrentHashMap，ConcurrentHashMap相比于HashTable，优秀的地方在于提供了分段锁。它会将整张表分为一个个的segment，然后每一个segment都相当于一个单独的hashtable，在线程访问其中一个segment的时候，其他的segment也可以访问，实现了真正的并发访问。

<h2>Segment</h2>

ConcurrentHashMap里面有一个内部类Segment<code>final Segment<K,V>[] segments</code>，而setgment里面又包含了一个HashEntry的数组<code>transient volatile HashEntry<K,V>[] table</code>

两次hash，第一次确定segment，第二次确定bucket。然后用链表链接。

concurrencyLevel

在ConcurrentHashMap的构造函数中，相对于hashmap增加了一个concurrencyLevel参数，故名思意，这个参数就是并发度，就是代表可以有多少个线程并发访问，也代表拥有多少个segment，默认值为16（2的sshift次方）。

<h2>put</h2>

<ol>
<li>ConcurrentHashMap不支持key或者value为null</li>
<li>根据key的hash值，向右移动32-sshift位数，然后与segmentMask做与运算，得出索引值。</li>
<li>在得到索引后，使用unsafe的方式得到segment，然后再进行一次&运算得到HashEntry链表的位置，然后set</li>
</ol>

<h2>get</h2>

与put不同的是，get操作是不需要加锁的（如果value为null，会调用readValueUnderLock，只有这个步骤会加锁）

<h2>size</h2>

先给3次机会，不lock所有的Segment，遍历所有Segment，累加各个Segment的大小得到整个Map的大小，如果某相邻的两次计算获取的所有Segment的更新的次数（每个Segment都有一个modCount变量，这个变量在Segment中的Entry被修改时会加一，通过这个值可以得到每个Segment的更新操作的次数）是一样的，说明计算过程中没有更新操作，则直接返回这个值。如果这三次不加锁的计算过程中Map的更新次数有变化，则之后的计算先对所有的Segment加锁，再遍历所有Segment计算Map大小，最后再解锁所有Segment。

<h1>HashSet</h1>

hashset内部使用了hashmap作为底层实现
HashSet实现了Set接口，它不允许集合中有重复的值，当我们提到HashSet时，第一件事情就是在将对象存储在HashSet之前，要先确保对象重写equals()和hashCode()方法，这样才能比较对象的值是否相等，以确保set中没有储存相等的对象。如果我们没有重写这两个方法，将会使用这个方法的默认实现。
HashSet不允许null，HashMap允许有null 。HashSet在add前，先调用hashcode和equals函数，判断是否有重复的值，没有再添加。

<h1>LinkedHashMap</h1>

LinkedHashMap同样是非线程安全的，只在单线程环境下使用。
这个建议结合源码来看。
将所有插入到该LinkedHashMap中的Entry按照插入的先后顺序依次加入到以head为头结点的双向循环链表的尾部。
LinkedHashMap是如何实现LRU的。首先，当accessOrder为true时，才会开启按访问顺序排序的模式，才能用来实现LRU算法。我们可以看到，无论是put方法还是get方法，都会导致目标Entry成为最近访问的Entry，因此便把该Entry加入到了双向链表的末尾（get方法通过调用recordAccess方法来实现，put方法在覆盖已有key的情况下，也是通过调用recordAccess方法来实现，在插入新的Entry时，则是通过createEntry中的addBefore方法来实现），这样便把最近使用了的Entry放入到了双向链表的后面，多次操作后，双向链表前面的Entry便是最近没有使用的，这样当节点个数满的时候，删除的最前面的Entry(head后面的那个Entry)便是最近最少使用的Entry。