java常用集合的理解，HMap,ConcurrentHashMap,List,set

1.HashMap 的底层数据结构以及扩容机制是怎样的？

底层数据结构:

JDK1.8 之前 HashMap 底层是 数组和链表 结合在一 起的,数组里每个存储的对象是Entry<key，value>对象，每个Entry<key，value>对象都包含一个对下个元素的引用,类似于拉链. 当HashMap 调用put方法增加元素时,首先调用 key 的 hashCode方法,然后再通过位运算处理过后得到 hash 值.,这是为了防止一些实现比较差的 hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞,能够最大限度使用数组空间,减少浪费

int hash = hash(key) //调用方法算出hash//求出Hash值
final int hash(Object k) {int h = hashSeed;if (0 != h && k instanceof String) {return sun.misc.Hashing.stringHash32((String) k);}h ^= k.hashCode();// 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 & (n - 1)  判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在 元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话,直接覆盖,不相同就通过拉链法解决冲突,把最新的数据放在最前面老的数据往后面移位,因为操作系统总是认为最近使用的数据会最容易被使用。

同样get方法调用时是通过key的hash值经过位运算，然后再&运算求出数组下标。取出链条。链条只有一条数据就是这个数据。如果不是就需要遍历链条上的数据(通过hashCode和equls方法判断)取出对应的key的value值。

public V put(K key, V value) {if (table == EMPTY_TABLE) {inflateTable(threshold);}if (key == null)return putForNullKey(value);int hash = hash(key);   //算出hash值int i = indexFor(hash, table.length); //求出数组下标for (Entry<K,V> e = table[i]; e != null; e = e.next) {Object k;//通过这个key的hashCode和equals方法来判断当前的key是否存在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;}int i = indexFor(hash, table.length)//调用方法获取数组下标值//通过hash值和数组长度length-1的与运算求出数组下标值
static int indexFor(int h, int length) {// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";return h & (length-1);}//创建数组元素ENtry对象
void createEntry(int hash, K key, V value, int bucketIndex) {Entry<K,V> e = table[bucketIndex];table[bucketIndex] = new Entry<>(hash, key, value, e);size++;}

HashMap的内存数组结构,每个数组元素下面会链条元素，数组加链表的结构，最新put进来的元素总是放在最上面,老的元素往后面移位。

JDK1.8 之后   开始默认数据结构也是数组和链表,数组里面的元素不再是Entry<key，value>对象,而是Node<key，value>对象(Node<key,value>实现了Map.Entry<key,value>接口,属性跟原来差不多)。当链表长度大于阈值（默认为 8）减1时，会首先调用 treeifyBin()方法。这个方法会根据 HashMap 数组来决定是否转换为红黑树。只有当数组长度大于或者等于 64 的情况下，才会 执行转换红黑树操作，以减少搜索时间。否则，就是只是执行 resize() 方法对数组扩容。之所以要达到64长度是因为只有达到这个长度时才能体现红黑树的搜索效率比之前的结构要快。当放入元素产生hash冲突时是往链条下面放元素(jdk1.7之前是使用头插法,JDK1.8使用尾插法)

 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length; //初始化长度为16if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {Node<K,V> e; K k;//判断元素是否存在的条件跟JDK8之前一样if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {//新放入的元素是往链条下面移位,而不是在JDK8之前新放进去数据在最前面。p.next = newNode(hash, key, value, null);//当链表长度到达阈值才会调用treeifyBin(tab, hash)方法if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;}//这个方法最终判断是否需要转红黑树
final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)//数组长度是否大于64，比                //64小就扩容resize();else if ((e = tab[index = (n - 1) & hash]) != null) {TreeNode<K,V> hd = null, tl = null;do {TreeNode<K,V> p = replacementTreeNode(e, null);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);//转换红黑树}}

扩容机制:

jdk8之前和之后扩容机制差不多是一样的，当元素数量超过阈值时便会触发扩容。每次扩容的容量都是之前容量的 2 倍HashMap 的容量是有上限的，必须小于 1<<30，即 1073741824。如果容量超出了这个 数，则不再增长，且阈值会被设置为 Integer.MAX_VALUE。这个阈值是数组的长度length * 负载因子(默认是0.75f).扩容后会重新计算旧数组中元素的存储位置。元素在新数组中的位置只有两种，原下标位置或原下标+旧数组的大小

值得注意的是 jdk1.8中红黑树和链表会相互转换,当链表小于8时会转换为链表,反之则转换红黑树。

后记：之所以选择红黑树是为了解决二叉查找树的缺陷，二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成很深的问题），遍历查找会非常慢。而红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，引入红黑树就是为了查找数据快，解决链表查询深度的问题，我们知道红黑树属于平衡二叉树，但是为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少，所以当长度大于8的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢

void addEntry(int hash, K key, V value, int bucketIndex) {Entry<K,V> e = table[bucketIndex];table[bucketIndex] = new Entry<K,V>(hash, key, value, e);if (size++ >= threshold)//threshold 值等于数组长度 * 负载因子resize(2 * table.length); //扩容是2倍长度}

public ConcurrentHashMap(int initialCapacity,float loadFactor, int concurrencyLevel) {if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)throw new IllegalArgumentException();if (concurrencyLevel > MAX_SEGMENTS)concurrencyLevel = MAX_SEGMENTS;// Find power-of-two sizes best matching argumentsint sshift = 0;int ssize = 1;while (ssize < concurrencyLevel) {++sshift;ssize <<= 1;}segmentShift = 32 - sshift;segmentMask = ssize - 1;this.segments = Segment.newArray(ssize);if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;int c = initialCapacity / ssize;if (c * ssize < initialCapacity)++c;int cap = 1;while (cap < c)cap <<= 1;for (int i = 0; i < this.segments.length; ++i)//初始化Segments数组中每个对象this.segments[i] = new Segment<K,V>(cap, loadFactor);}//put方法存入元素
V put(K key, int hash, V value, boolean onlyIfAbsent) {lock();//每个Segment对象进来是锁住try {int c = count;if (c++ > threshold) // ensure capacityrehash();//扩容机制和HahshMap一样HashEntry<K,V>[] tab = table;int index = hash & (tab.length - 1);HashEntry<K,V> first = tab[index];HashEntry<K,V> e = first;while (e != null && (e.hash != hash || !key.equals(e.key)))e = e.next;V oldValue;if (e != null) {oldValue = e.value;if (!onlyIfAbsent)e.value = value;}else {oldValue = null;++modCount;tab[index] = new HashEntry<K,V>(key, hash, first, value);count = c; // write-volatile}return oldValue;} finally {unlock();}}