点击查看Java集合类合集
JDK7中HashMap的底层实现是哈希表（数组加链表实现）。当要向HashMap中添加新的元素时，先根据某种算法计算出key的hash值，并根据hash值和数组容量通过某种算法得出下标（&运算），当发生冲突时，将遍历相应位置的链表，如果key值重复，则将新的value覆盖老的value，并将老value值返回。如果key值不存在，则用头插法插入链表。key可以为null，此时将把元素的放到下标为0的链表中。当哈希表中数据个数超过阈值且，新元素要插入的位置已经存在元素时，将进行扩容。 Entry是哈希表中实际存储数据的对象，他是一个HashMap的静态类 HashMap存储数据不保证有序 (有些源码解释我以注解的形式写到了源码中) 示意图
static class Entry<K, V> implements java.util.Map.Entry<K, V> { final K key; V value; HashMap.Entry<K, V> next; int hash; Entry(int var1, K var2, V var3, HashMap.Entry<K, V> var4) { this.value = var3; this.next = var4; this.key = var2; this.hash = var1; }他有4个属性，分别是 key value hash 和 next指针
创建HashMap对象时，可以传入两个参数，第一个参数val1为用户期望的哈希表数组容量（注意不是阈值，虽然在一开始会把这个值赋给阈值属性，但是添加属性时会改。也不宜一定是真正的数组容量），第二个参数val2为加载因子（用来计算阈值）。va1需要大于等于0.val2要大于等于0.
HashMap的数组容量需要为2的幂次数（如1 2 4 8 16）。将根据传入的参数计算出一个大于等于参数的2的幂次数作为数组大小。同时计算阈值（数组大小*加载因子）代码如下
private void inflateTable(int var1) { int var2 = roundUpToPowerOf2(var1);//获取数组大小 this.threshold = (int)Math.min((float)var2 * this.loadFactor, 1.07374182E9F);//获取阈值 this.table = new HashMap.Entry[var2];//初始化数组 this.initHashSeedAsNeeded(var2);//设置hashSeed值（一般情况下均为默认值0） } private static int roundUpToPowerOf2(int var0) { return var0 >= 1073741824 ? 1073741824 : (var0 > 1 ? Integer.highestOneBit(var0 - 1 << 1) : 1); } public static int highestOneBit(int var0) { var0 |= var0 >> 1; var0 |= var0 >> 2; var0 |= var0 >> 4; var0 |= var0 >> 8; var0 |= var0 >> 16; return var0 - (var0 >>> 1); }当第一次添加元素时，将进行哈希表的初始化
public V put(K var1, V var2) { //如果是第一次添加元素，将进入这个if if (this.table == EMPTY_TABLE) { this.inflateTable(this.threshold);//初始化哈希表(代码见上面) } //key值为null时将把他放入下标为0的链表中，同时检测是否已经存在null值key if (var1 == null) { return this.putForNullKey(var2); } else { //根据哈希算法计算哈希值 int var3 = this.hash(var1); // 根据哈希值和数组大小计算下标 int var4 = indexFor(var3, this.table.length); //遍历相应数组下标的链表，判断key值是否重复，若重复则覆盖并返回旧value，若不重复则继续执行 for(HashMap.Entry var5 = this.table[var4]; var5 != null; var5 = var5.next) { Object var6; if (var5.hash == var3 && ((var6 = var5.key) == var1 || var1.equals(var6))) { Object var7 = var5.value; var5.value = var2; var5.recordAccess(this); return var7; } } //对哈希表的操作计数（预防错误） ++this.modCount; //进行添加操作 this.addEntry(var3, var1, var2, var4); return null; } }哈希算法 将key的hashCode算法返回的哈希值进行右移操作，然后在进行亦或运算（让哈希值高位也参与到运算中来，防止因为哈希值高位发生变化而实际计算出的下标都相同的情况）
final int hash(Object var1) { int var2 = this.hashSeed; if (0 != var2 && var1 instanceof String) { return Hashing.stringHash32((String)var1); } else { var2 ^= var1.hashCode(); var2 ^= var2 >>> 20 ^ var2 >>> 12; return var2 ^ var2 >>> 7 ^ var2 >>> 4; } }计算数组下标算法 用哈希值与数组长度-1进行&运算。都到的值为【0，数组长度-1】
static int indexFor(int var0, int var1) { return var0 & var1 - 1; }当key值不重复时，将进行头插法插入。此时需要进行扩容检测
void addEntry(int var1, K var2, V var3, int var4) { //当哈希表元素个数，大于等于阈值，并且，当前要添加位置不为null时，进行扩容。 if (this.size >= this.threshold && null != this.table[var4]) { this.resize(2 * this.table.length); var1 = null != var2 ? this.hash(var2) : 0; var4 = indexFor(var1, this.table.length); } //真正的添加方法 this.createEntry(var1, var2, var3, var4); }添加元素方法
void createEntry(int var1, K var2, V var3, int var4) { HashMap.Entry var5 = this.table[var4]; this.table[var4] = new HashMap.Entry(var1, var2, var3, var5); ++this.size; }根据传入的哈希值 ，key ,value 数组下标来添加新元素。（头插）
将阈值重新计算，并执行扩容
void resize(int var1) { HashMap.Entry[] var2 = this.table; int var3 = var2.length; if (var3 == 1073741824) { this.threshold = 2147483647; } else { HashMap.Entry[] var4 = new HashMap.Entry[var1]; //将原来的数组复制到新的数组中，第二个参数为是否需要重新哈希 //如果this.initHashSeedAsNeeded(var1)返回true则说明HashSeed可能改变了，因此需要重新计算哈希值 this.transfer(var4, this.initHashSeedAsNeeded(var1)); this.table = var4; this.threshold = (int)Math.min((float)var1 * this.loadFactor, 1.07374182E9F); } } void transfer(HashMap.Entry[] var1, boolean var2) { int var3 = var1.length; HashMap.Entry[] var4 = this.table; int var5 = var4.length; HashMap.Entry var8; for(int var6 = 0; var6 < var5; ++var6) { for(HashMap.Entry var7 = var4[var6]; null != var7; var7 = var8) { var8 = var7.next; if (var2) { var7.hash = null == var7.key ? 0 : this.hash(var7.key); } int var9 = indexFor(var7.hash, var3); var7.next = var1[var9]; var1[var9] = var7; } } }将原来的元素重新计算下标（或者重新计算哈希值再计算下标）。然后将entry对象放到新的数组中。
如果key为nul，就去数组下标为0的位置寻找，当key等于null时，就返回。
private V getForNullKey() { if (this.size == 0) { return null; } else { for(HashMap.Entry var1 = this.table[0]; var1 != null; var1 = var1.next) { if (var1.key == null) { return var1.value; } } return null; } }如果key不为null，则根据计算出key的哈希值，根据哈希值和数组大小计算出下标。然后去相应下标处寻找。
final HashMap.Entry<K, V> getEntry(Object var1) { if (this.size == 0) { return null; } else { //计算哈希值 int var2 = var1 == null ? 0 : this.hash(var1); for(HashMap.Entry var3 = this.table[indexFor(var2, this.table.length)]; var3 != null; var3 = var3.next) { Object var4; if (var3.hash == var2 && ((var4 = var3.key) == var1 || var1 != null && var1.equals(var4))) { return var3; } } return null; } }根据key值删除哈希表中的元素。先将key值进行哈希，再利用哈希值和数组大小算出数组下标。然后遍历链表找到相应元素删除。
public V remove(Object var1) { HashMap.Entry var2 = this.removeEntryForKey(var1); return var2 == null ? null : var2.value; } final HashMap.Entry<K, V> removeEntryForKey(Object var1) { if (this.size == 0) { return null; } else { //如果key为null //哈希值和数组下标均为0 int var2 = var1 == null ? 0 : this.hash(var1); int var3 = indexFor(var2, this.table.length); HashMap.Entry var4 = this.table[var3]; HashMap.Entry var5; HashMap.Entry var6; for(var5 = var4; var5 != null; var5 = var6) { var6 = var5.next; Object var7; if (var5.hash == var2 && ((var7 = var5.key) == var1 || var1 != null && var1.equals(var7))) { //操作量加1 ++this.modCount; //HashMap元素数减一 --this.size; if (var4 == var5) { //如果头节点为要删除的元素 this.table[var3] = var6; } else { //如果中间节点为要删除的元素 var4.next = var6; } //JDK1.7中为空方法 var5.recordRemoval(this); return var5; } var4 = var5; } return var5; } }HashMap是线程不安全的。 1.扩容时的并发问题 如果两个线程在给同一个HashMap赋值时，都发生了扩容。因为利用头插法扩展数组，所以在转移数据的时候，老数组的链表会逆序放入新数组（假设移动后下标都没变）。如果一个线程已经完成了转移，此时另一个线程的next对象引用和当前要转移的对象引用，的顺序就倒过来了，这个时候再进行转移，链表将会出现环。 2.遍历时的并发问题 当有两个线程一个进行读取一个进行修改时，也会产生并发问题。（modCount改变）
当对HashMap进行增删操作时，均会使modCount递增。java规定在利用迭代器进行便利的时候应该保持容器的稳定，即不能在使用迭代器期间进行增删操作。而modeCount就是用来完成这件事的。当迭代器被创建的时候，将初始化this.expectedModCount = HashMap.this.modCount;。再利用迭代器进行操作时，会判断这两个量是否相等。如果在利用迭代器期间对容器进行了操作就会导致modCount递增，这时就和expectedModCount不当等，这时就会抛出异常throw new ConcurrentModificationException();
//创建迭代器 private abstract class HashIterator<E> implements Iterator<E> { HashMap.Entry<K, V> next; int expectedModCount; int index; HashMap.Entry<K, V> current; HashIterator() { //记录modCount this.expectedModCount = HashMap.this.modCount; if (HashMap.this.size > 0) { HashMap.Entry[] var2 = HashMap.this.table; while(this.index < var2.length && (this.next = var2[this.index++]) == null) { } } } //利用迭代器删除元素 public void remove() { if (this.current == null) { throw new IllegalStateException(); //判断是否相等（是否进行了增删） } else if (HashMap.this.modCount != this.expectedModCount) { throw new ConcurrentModificationException(); } else { Object var1 = this.current.key; this.current = null; HashMap.this.removeEntryForKey(var1); this.expectedModCount = HashMap.this.modCount; } } }例子
public class Test1 { public static void main(String[] args) { HashMap hashMap = new HashMap(); hashMap.put("k1",1); hashMap.put("k2",2); hashMap.put("k3",2); Set set = hashMap.keySet(); Iterator iterator = set.iterator(); while(iterator.hasNext()) { Object o = iterator.next(); System.out.println(o); set.remove("k1"); } } }modCount是int类型。在java中int类型是4位32字节。如果对HashMap一直操作的话，要是他到了最大值之后怎么办呢？ —————————— 经过测试，他变成最大之后，会从MIN_VALUE开始增加，这个检测依旧能正常进心。
