1、HashMap的数据结构(HashMap通过hashcode对其内容进行高速查找，是无序的)
数据结构中有数组和链表来实现对数据的存储，但这两者基本上是两个极端。
数组 ：数组的存储区是连续的，占用内存严重，故空间复杂度非常大。但数组的二分查找时间度小；数组的特点：寻址easy，插入和
删除困难。
链表 ：链表的储存区离散。占用内存比較宽松。故空间复杂度非常小，但时间复杂度大；链表的特点：寻址困难，插入和删除easy。哈希表
HashMap是由数组+链表组成。寻址easy，插入和删除easy。（存储单元数组Entry[]，数组里面包括链表）
HashMap事实上也是由一个线性的数组实现的。
所以能够理解为其存储数据的容器就是一个线性容器；
HashMap里面有一个内部静态类Entry，其重要的属性有key，value，next，从属性key，value 就能够非常明显的看出来 Entry就是
HashMap键值对实现的一个基础bean；也就是说HashMap的基础就是一个线性数组，这个数组就是Entry[]。Map里面的内容都保存
在Entry[]中；
/** * The table, resized as necessary. Length MUST Always be a power of two. */ transient Entry[] table;
2、HashMap的存取实现
2.1：存储
这里HashMap用了一个算法。
//存储时候：
int hash=key.hashCode(); //获取key的hashCode，这个值是一个固定的int值
int index=hash%Entry[].length。//获取数组下标：key的hash值对Entry数组长度进行取余
Entry[index]=value。注意：假设两个key通过hash%Entry[].length得到的index同样。会不会覆盖？
是不会的。Entry类有一个next属性，作用是指向下一个Entry。打个例如， 第一个键值对A进来。通过计算其key的hash得到的
index=0。记做:Entry[0] = A。一会后又进来一个键值对B，通过计算其index也等于0，如今怎么办？HashMap会这样做:B.next =
A,Entry[0] = B,假设又进来C,index也等于0,那么C.next = B,Entry[0] = C；这样我们发现index=0的地方事实上存取了A,B,C三个键值对,他
们通过next这个属性链接在一起。
所以疑问不用操心。
也就是说Entry[]数组中存储的是最后插入的数据
public V put(K key, V value) { if (key == null) return putForNullKey(value); //null总是放在数组的第一个链表中 int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); //遍历链表 for (Entry e = table[i]; e != null; e = e.next) { Object k; //假设key在链表中已存在，则替换为新value 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; } void addEntry(int hash, K key, V value, int bucketIndex) { Entry e = table[bucketIndex]; table[bucketIndex] = new Entry (hash, key, value, e); //參数e, 是Entry.next //假设size超过threshold，则扩充table大小。再散列 if (size++ >= threshold) resize(2 * table.length); } 2.2：取值
获取key的hashcode指，通过hash值去hash%Entry[].length 获取Entry[hash%Entry[].length]，定位到该数组元素之后，再遍历该元
素处的链表。
//取值时候：int hash=key.hashCode();
int index =hash%Entry[].length;
return Entry[index];
public V get(Object key) { if (key == null) return getForNullKey(); int hash = hash(key.hashCode()); //先定位到数组元素。再遍历该元素处的链表 for (Entry 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; } 当哈希表的容量超过默认容量时，必需要调整table的大小。
当容量达到最大值时，该方法Integer.MAX_VALUE返回。这时。就需要创建
一张表，将原来的表映射到新表中。
3、HashMap、HashTable和ConcurrentHashMap的线程安全问题
HashMap：线程不安全的。
HashTable：锁住整张hash表，让线程独占。hashMap同意为空。通过分析Hashtable就知道，synchronized是针对整张Hash表的，即每次锁住整张表
让线程独占。安全的背后是巨大的浪费。
ConcurrentHashMap:一个更快的hashmap，它提供了好得多的并发性。多个读操作差点儿总能够并发地运行。
他是锁段（默认：把hash表分为16个
段），在get，put，remove等操作中，ConcurrentHashMap仅仅锁定当前须要用到的段，仅仅有在求size的时候才锁定整张hash表。