数据结构
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-value
boolean containsKey(Object key); // 判断是否存在该 key 的 key-value 对；是则返回 true
boolean containsValue(Object value); // 判断是否存在该 value 的 key-value 对；是则返回 true
Set<K> keySet(); // 独自抽取 key 序列，将所有 key 生成一个 Set
Collection<V> values(); // 独自 value 序列，将所有 value 生成一个 Collection
void 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