数据结构
JDK1.7的HashMap采纳数组+单链表的数据结构，数组和链表存储的是一个个Entry对象
static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; int hash;}罕用办法
V get(Object key); //取得指定key的值V put(K key, V value); //增加key-value对void putAll(Map<? extends K, ? extends V> m); //将指定Map中的key-value对复制到此Map中V remove(Object key); //删除该key-valueboolean containsKey(Object key); //判断是否存在该key的key-value对；是则返回trueboolean containsValue(Object value); //判断是否存在该value的key-value对；是则返回true Set<K> keySet(); //独自抽取key序列，将所有key生成一个SetCollection<V> values(); //独自value序列，将所有value生成一个Collectionvoid clear(); // 革除HashMap中的所有key-value对int size(); // 返回HashMap中所有key-value对的数量boolean isEmpty(); // 判断HashMap是否为空,size == 0时示意为空 应用
public class HashMapTest { public static void main(String[] args) { /** * 1. 申明1个 HashMap的对象 */ Map<String, Integer> map = new HashMap<String, Integer>(); /** * 2. 向HashMap增加数据（放入键-值对） */ map.put("Java", 1); map.put("HashMap", 2); map.put("List",3); map.put("set",4); /** * 3. 获取 HashMap 的某个数据 */ System.out.println("" + map.get("HashMap")); /** * 4. 遍历HashMap共有3种办法：别离针对Entry或key或value * 步骤1：取得Entry或key或value的汇合 * 步骤2：遍历，应用for循环或迭代器Iterator */ // 办法1：取得Entry的Set汇合再遍历 // 取得Entry的Set汇合 Set<Map.Entry<String, Integer>> entrySet = map.entrySet(); // 通过for循环遍历 for(Map.Entry<String, Integer> entry : entrySet){ System.out.print(entry.getKey()); System.out.println(entry.getValue()); } // 通过迭代器遍历 // 先取得Entry的Iterator，再循环遍历 Iterator iter1 = entrySet.iterator(); while (iter1.hasNext()) { // 遍历时，需先获取entry，再别离获取key、value Map.Entry entry = (Map.Entry) iter1.next(); System.out.print((String) entry.getKey()); System.out.println((Integer) entry.getValue()); } // 办法2：取得key的Set汇合再遍历 Set<String> keySet = map.keySet(); // 通过for循环 for(String key : keySet){ System.out.print(key); System.out.println(map.get(key)); } // 通过迭代器遍历 // 先取得key的Iterator，再循环遍历 Iterator iter2 = keySet.iterator(); String key = null; while (iter2.hasNext()) { // 遍历时，需先获取key，再获取value key = (String)iter2.next(); System.out.print(key); System.out.println(map.get(key)); } // 办法3：取得value的汇合再遍历 Collection valueSet = map.values(); // 取得values的Iterator，再循环遍历 Iterator iter3 = valueSet.iterator(); while (iter3.hasNext()) { System.out.println(iter3.next()); } }}对于遍历形式，举荐应用针对 key-value对（Entry）的形式：效率高
- 对于遍历keySet,valueSet，本质上遍历了2次：
第1次，for/iterator迭代器遍历;
第2次 从HashMap中取出key的value操作 - 对于遍历entrySet，本质遍历了1次for/iterator迭代器遍历，Entry曾经存储了key和 value
源码剖析
次要属性
//默认容量static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;//最大容量static final int MAXIMUM_CAPACITY = 1 << 30;//加载因子static final float DEFAULT_LOAD_FACTOR = 0.75f;//扩容阈值 = 容量 x 加载因子，当哈希表的大小 ≥ 扩容阈值时，就会扩容哈希表int threshold//存储数据的Entry类型数组，长度=2的幂transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE//HashMap中存储的键值对的数量transient int size构造方法
//加载因子，容量可指定 public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; threshold = initialCapacity; init(); } //加载因子等于默认值，容量可指定 public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } //默认构造函数，加载因子，容量等于默认值 public HashMap() { this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); } //可传入一个map的构造函数 public HashMap(Map<? extends K, ? extends V> m) { this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); inflateTable(threshold); putAllForCreate(m); }put()办法
public V put(K key, V value) { //1.若entry数组为空，则初始化数组 if (table == EMPTY_TABLE) { inflateTable(threshold); } //2.若key == null，则将该键-值 寄存到entry数组中的第1个地位，即table[0] if (key == null) return putForNullKey(value); //3.若 key ≠ null，则计算寄存entry数组中的地位 //3.1依据键值key计算hash值 int hash = hash(key); //3.2依据hash值 最终取得 key对应寄存的entry数组中地位 int i = indexFor(hash, table.length); 4. 通过遍历以该数组元素为头结点的链表,判断该key值是否已存在 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; 4.1 若该key已存在，则用新value替换旧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++; //4.2 若该key不存在，则将key-value增加到entry数组中,这里采纳头插法 addEntry(hash, key, value, i); return null; }addEntry resize() transfer()
void addEntry(int hash, K key, V value, int bucketIndex) { // 若不足够，则进行扩容（2倍),从新计算Hash值、从新计算key在扩容后的entry数组下标 if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length); hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } //若容量足够，则创立1个新的数组元素Entry并放入到entry数组中 createEntry(hash, key, value, bucketIndex); } void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } //依据新容量（2倍容量）新建1个entry数组，newtable Entry[] newTable = new Entry[newCapacity]; //将旧entry数组上的entry数据转移到newtable中，从而实现扩容 transfer(newTable, initHashSeedAsNeeded(newCapacity)); //新数组table援用到HashMap的table属性上 table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); } //旧entry数组上的entry数据转移到newtable中，从而实现扩容，按旧链表的正序遍历链表，在新链表的头部顺次插入， //即扩容前 = 1->2->3，扩容后 = 3->2->1，此时若（多线程）并发执行 `put（）操作，一旦呈现扩容状况，则容易呈现环形链表，从而在获取数据、遍历链表时造成死循环Infinite Loop void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry<K,V> e : table) { while(null != e) { Entry<K,V> next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } } }get()办法
public V get(Object key) { //当key == null时，则到以entry数组中的第1个元素（即table[0]）为头结点的链表去寻找对应 key == null的键 if (key == null) return getForNullKey(); //当key ≠ null时，去取得对应值 Entry<K,V> entry = getEntry(key); return null == entry ? null : entry.getValue(); } final Entry<K,V> getEntry(Object key) { if (size == 0) { return null; } // 1. 依据key值，通过hash（）计算出对应的hash值 // 2. 依据hash值计算出对应的数组下标 // 3. 遍历以该数组下标的数组元素为头结点的链表所有节点，寻找该key对应的值 int hash = (key == null) ? 0 : hash(key); for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } return null; }源码总结
1.JDK1.7的HashMap采纳数组+单链表的数据结构，数组和链表存储的是一个个Entry对象
2.增加key-value时会依据key值计算出对应的hash值，再依据hash值计算出对应的数组下标，遍历这个数组中的Entry链表，如果存在有雷同的key的Entry,用新的value值替换旧的value值，若不存在则用头插法退出到链表中。
3.在增加key-value到数组中时有扩容的判断，但hashmap中Entry的数量，或者说key-value的数量大于扩容阈值 = 以后容量 x 加载因子，新建一个数组，容量时是数组的2倍，将旧entry数组上的entry数据转移到newtable中，让以后的数组指向新数组，从而实现扩容。
4.线程不平安问题：
在扩容过程中，在将旧数组上的数据转移到新数组上时，按旧链表的正序遍历链表，在新链表的采纳头插法插入，即扩容前 = 1->2->3，扩容后 = 3->2->1，此时若（多线程）并发执行 `put（）操作，一旦呈现扩容状况，则容易呈现环形链表，从而在get()办法获取数据、遍历链表时造成死循环Infinite Loop