HashMap和ConcurrentHashMap的区别：
- HashMap不是线程安全的，而ConcurrentHashMap是线程安全的。
-
ConcurrentHashMap采用锁分段技术，将整个Hash桶进行了分段segment，也就是将这个大的数组分成了几个小的片段segment，而且每个小的片段segment上面都有锁存在，那么在插入元素的时候就需要先找到应该插入到哪一个片段segment，然后再在这个片段上面进行插入，而且这里还需要获取segment锁。
- ConcurrentHashMap让锁的粒度更精细一些，并发性能更好。
HashMap的底层源码：
一. 数据结构
Map将实际数据存储在Entry类的数组中。
transient Entry[] table; //HashMap的成员变量，存放数据 static class Entry<K,V> implements Map.Entry<K,V> { //内部类Entry final K key; V value; Entry<K,V> next; //指向下一个数据 final int hash; /** * Creates new entry. */ Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; }
执行put方法时，根据key的hash值来计算放到table数组的下标，如果hash有相同的下标，则新put进去的元素放到Entry链的头部。
二. 属性和构造方法
属性：
1 static final int DEFAULT_INITIAL_CAPACITY = 16; //默认的初始大小，如果执行无参的构造方法，则默认初始大小为16 2 static final int MAXIMUM_CAPACITY = 1 << 30; //最大容量，1073741824 3 static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认的负载因子，如果没有通过构造方法传入负载因子，则使用0.75。 4 transient Entry[] table; //存放具体键值对的Entry数组 5 transient int size; //HashMap的大小 6 int threshold; //阀值 threshold = (int)(capacity * loadFactor); 即容量*负载因子，执行put方法时如果size大于threshold则进行扩容，后面put方法将会看到 7 final float loadFactor; //用户设置的负载因子 8 transient volatile int modCount; //HashMap实例被改变的次数，这个同ArrayList
构造方法一：
1 public HashMap() { 2 this.loadFactor = DEFAULT_LOAD_FACTOR; 3 threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); 4 table = new Entry[DEFAULT_INITIAL_CAPACITY]; 5 init(); 6 }
使用了默认的容量和默认的负载因子。
构造方法二：
1 public HashMap(int initialCapacity) { 2 this(initialCapacity, DEFAULT_LOAD_FACTOR); 3 }
使用了用户设置的初始容量和默认的负载因子。
构造方法三：
1 public HashMap(int initialCapacity, float loadFactor) { 2 if (initialCapacity < 0) 3 throw new IllegalArgumentException("Illegal initial capacity: " + 4 initialCapacity); 5 if (initialCapacity > MAXIMUM_CAPACITY) 6 initialCapacity = MAXIMUM_CAPACITY; 7 if (loadFactor <= 0 || Float.isNaN(loadFactor)) 8 throw new IllegalArgumentException("Illegal load factor: " + 9 loadFactor); 10 11 // Find a power of 2 >= initialCapacity 12 int capacity = 1; 13 while (capacity < initialCapacity) 14 capacity <<= 1; 15 16 this.loadFactor = loadFactor; 17 threshold = (int)(capacity * loadFactor); 18 table = new Entry[capacity]; 19 init(); 20 }
用户传入了初始容量和负载因子，这两个值是HashMap性能优化的关键，涉及到了HashMap的扩容问题。
HashMap的容量永远是2的倍数，如果传入的不是2的指数则被调整为大于传入值的最近的2的指数，例如如果传入130，则capacity计算后是256。是这段代码起的作用：
1 while (capacity < initialCapacity) 2 capacity <<= 1;
构造方法四：
1 public HashMap(Map<? extends K, ? extends V> m) { 2 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, 3 DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);//计算Map的大小 4 putAllForCreate(m);//初始化 5 } 6 7 private void putAllForCreate(Map<? extends K, ? extends V> m) { 8 for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {//通过entryset进行遍历 9 Map.Entry<? extends K, ? extends V> e = i.next(); 10 putForCreate(e.getKey(), e.getValue()); 11 } 12 }
根据传入的map进行初始化。
三. 关键方法
1) put方法
1 public V put(K key, V value) { 2 if (key == null) 3 return putForNullKey(value); //单独处理，总是放到table[0]中 4 int hash = hash(key.hashCode()); //计算key的hash值，后面介绍性能的时候再说这个hash方法。 5 int i = indexFor(hash, table.length); //将hash和length-1取&来得到数组的下表 6 for (Entry<K,V> e = table[i]; e != null; e = e.next) { 7 Object k; 8 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 9 V oldValue = e.value; 10 e.value = value; 11 e.recordAccess(this); 12 return oldValue; 13 } 14 } //如果这个key值，原来已经则替换后直接返回。 15 modCount++; 16 addEntry(hash, key, value, i); 17 return null; 18 } 19 void addEntry(int hash, K key, V value, int bucketIndex) { 20 Entry<K,V> e = table[bucketIndex]; 21 table[bucketIndex] = new Entry<K,V>(hash, key, value, e); //如果table[bucketIndex]中已经存在Entry则放到头部。 22 if (size++ >= threshold) //如果大于了阀值，则扩容到原来大小的2倍。 23 resize(2 * table.length); 24 } 25 26 void resize(int newCapacity) { 27 Entry[] oldTable = table; 28 int oldCapacity = oldTable.length; 29 if (oldCapacity == MAXIMUM_CAPACITY) { 30 threshold = Integer.MAX_VALUE; 31 return; 32 } 33 34 Entry[] newTable = new Entry[newCapacity]; 35 transfer(newTable); //赋值到新的table中，注意转移后会重新hash，所以位置可能会跟之前不同，目的是均匀分不到新的table中。 36 table = newTable; 37 threshold = (int)(newCapacity * loadFactor); 38 }
2) get方法
1 public V get(Object key) { 2 if (key == null) 3 return getForNullKey(); 4 int hash = hash(key.hashCode()); 5 for (Entry<K,V> e = table[indexFor(hash, table.length)];//找到数组的下表，进行遍历 6 e != null; 7 e = e.next) { 8 Object k; 9 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) 10 return e.value;//找到则返回 11 } 12 return null;//否则，返回null 13 }
3) remove方法
1 public V remove(Object key) { 2 Entry<K,V> e = removeEntryForKey(key); 3 return (e == null ? null : e.value); 4 } 5 6 final Entry<K,V> removeEntryForKey(Object key) { 7 int hash = (key == null) ? 0 : hash(key.hashCode()); 8 int i = indexFor(hash, table.length); 9 Entry<K,V> prev = table[i]; 10 Entry<K,V> e = prev; 11 12 while (e != null) {//Entry链未遍历完则一直遍历 13 Entry<K,V> next = e.next; 14 Object k; 15 if (e.hash == hash && 16 ((k = e.key) == key || (key != null && key.equals(k)))) { 17 modCount++; 18 size--; 19 if (prev == e)//如果是第一个，则将table[i]执行e.next 20 table[i] = next; 21 else //否则将前一个的next指向e.next 22 prev.next = next; 23 e.recordRemoval(this); 24 return e; 25 } 26 prev = e;//未找到则继续往后遍历 27 e = next; 28 } 29 30 return e; 31 }
4) HashMap的遍历方法
1 Map map = new HashMap(); 2 map.put("key1","value1"); 3 map.put("key2","value2"); 4 map.put("key3", "value3"); 5 for(Iterator it = map.entrySet().iterator();it.hasNext();){ 6 Map.Entry e = (Map.Entry)it.next(); 7 System.out.println(e.getKey() + "=" + e.getValue()); 8 } 9 System.out.println("-----------------------------------------"); 10 for(Iterator it = map.keySet().iterator();it.hasNext();){ 11 Object key = it.next(); 12 Object value = map.get(key); 13 System.out.println(key+"="+value); 14 } 15 System.out.println("-----------------------------------------"); 16 System.out.println(map.values()); 17 18 输出为： 19 key3=value3 20 key2=value2 21 key1=value1 22 ----------------------------------------- 23 key3=value3 24 key2=value2 25 key1=value1 26 ----------------------------------------- 27 [value3, value2, value1]