1. class 简介
HashMap和HashSet是使用非常广泛的java集合，其中HashSet本质上就是一个HashMap。数组以整数索引作为下标，而HashMap相当于把任意对象作为下标（中途通过哈希函数转换成哈希地址），实现了常量时间的随机访问，当哈希地址冲突时（机率很小），使用链地址法解决冲突。主要方法有put，get，remove，containsKey，containsValue，keySet，entrySet等方法。
2. class内部原理及特点
不是线程安全的。键和值都允许为null，规定null键对应的哈希地址为0（桶下标）。键不会出现重复，但值可以出现重复。内部是一个循环数组Entry[] table，数组中每个元素都是一条单链表，数组默认初始容量为16（数量一定为2的幂，方便快速取余，循环使用数组），最大容量为2^30；默认负载因子为0.75（是时间和空间的折衷），负载因子与容量的乘积为阈值，超过阈值会扩容，然后重构哈希表，创建一个新的Entry数组，将旧Entry[]的非null键值对一个一个重新计算哈希地址复制到新的Entry数组中，代价很高昂。所以可以预估一下所需HashMap的容量大小。HashMap并没有使用自带的hashCode直接作为数组（桶）的下标，而是通过一个额外的hash函数将其再次打乱，进一步降低哈希地址出现冲突的机率，提高哈希表的性能对HashMap进行迭代会遍历整个Entry数组，但是数组中很多位置是空的，当需要考虑迭代的性能时，不要把HashMap容量设置得太大，或者把负载因子设置得太小。其迭代器是快速失败的，在其迭代器创建之后调用非迭代器中的方法对容器的内部结构进行修改都会抛出ConcurrentModificationException。HashSet底层就是一个HashMap，只不过把元素全部保存在键上，值统一用一个PRESENT的Object对象占位，各种方法全部借用了HashMap，这也体现了组合的灵活。
3. class源码细节分析
先回忆一下数据结构哈希表的创建、添加键值对、根据键查找键值对、取得所有键和所有值的具体做法（用经典的timesXX哈希函数和链地址法）: 创建哈希表：创建一个指定长度的数组，数组类型为链表结点类型，结点包含键、值和指向下一个结点的引用。 添加键值对： 1、用timesXX算法计算出键的哈希地址作为循环数组的下标，如果下标超过了数组的最大下标，则对长度取余作为下标。 2、遍历数组当前下标对应的链表，中途将待添加键值对与链表结点的键进行比较，如果相同，说明之前添加过相同的键，则将新值覆盖结点的旧值，结束；如果遍历完成之后没有键没有相同的，说明是哈希码冲突了，此时将键值对添加到链表中。 根据键查找键值对： 1、用timesXX算法计算出键的哈希地址作为循环数组的下标，如果下标超过了数组的最大下标，则对长度取余作为下标。 2、遍历数组当前下标对应的链表，找到键相同的结点，接下来可以返回其中的值或者删除此结点。 取得所有键和所有值： 遍历整个数组，对数组中每个链表进行一一遍历 只要了解了哈希表数据结构的内部原理，看JDK中HashMap源码就不会存在任何问题。
基本成员变量
static final int DEFAULT_INITIAL_CAPACITY =
16;
static final int MAXIMUM_CAPACITY =
1 <<
30;
static final float DEFAULT_LOAD_FACTOR =
0.75f;
transient Entry[] table;
transient int size;
int threshold;
final float loadFactor;
transient int modCount;
创建HashMap
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);
int capacity =
1;
while (capacity < initialCapacity)
capacity <<=
1;
this.loadFactor = loadFactor;
threshold = (
int)(capacity * loadFactor);
table =
new Entry[capacity];
init();
}
hash函数和indexFor
static int hash(
int h) {
h ^= (h >>>
20) ^ (h >>>
12);
return h ^ (h >>>
7) ^ (h >>>
4);
}
static int indexFor(
int h,
int length) {
return h & (length-
1);
}
关于hash为何要右移和异或http://www.iteye.com/topic/709945
put
public V
put(K key, V
value) {
if (key ==
null)
return putForNullKey(
value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e !=
null; e = e.next) {
Object k;
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;
}
private V
putForNullKey(V
value) {
for (Entry<K,V> e = table[
0]; e !=
null; e = e.next) {
if (e.key ==
null) {
V oldValue = e.
value;
e.
value =
value;
e.recordAccess(
this);
return oldValue;
}
}
modCount++;
addEntry(
0,
null,
value,
0);
return null;
}
void addEntry(
int hash, K key, V
value,
int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] =
new Entry<>(hash, key,
value, e);
if (size++ >= threshold)
resize(
2 * table.length);
}
void resize(
int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable =
new Entry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (
int)(newCapacity * loadFactor);
}
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (
int j =
0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e !=
null) {
src[j] =
null;
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
while (e !=
null);
}
}
}
get
public V
get(Object key) {
if (key ==
null)
return getForNullKey();
int hash = hash(key.hashCode());
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.equals(k)))
return e.
value;
}
return null;
}
private V
getForNullKey() {
for (Entry<K,V> e = table[
0]; e !=
null; e = e.next) {
if (e.key ==
null)
return e.
value;
}
return null;
}
final Entry<K,V> getEntry(Object key) {
int hash = (key ==
null) ?
0 : hash(key.hashCode());
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;
}
getEntry和get方法差不多，get根据键返回值，getEntry根据键返回键值对。get方法如果返回null，并不能说明键值对不存在，因为有可能键值对中值正好是null；而getEntry返回null则只能说明键值对不存在，所以containsKey方法内部肯定是调用的getEntry。
public boolean containsKey(Object key) {
return getEntry(key) !=
null;
}
remove
public V
remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e ==
null ?
null : e.
value);
}
final Entry<K,V> removeEntryForKey(Object key) {
int hash = (key ==
null) ?
0 : hash(key.hashCode());
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
while (e !=
null) {
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key !=
null && key.equals(k)))) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(
this);
return e;
}
prev = e;
e = next;
}
return e;
}
４. 总结
HashMap和HashSet是非常强大的java集合，有着常量时间的随机访问操作，性能十分优越，但是这是建立在空间开销上的，其中会有很多闲置空间。如果空间小了会频繁rehash，空间大了又会造成浪费，所以还是要尽量预先估计所需空间大小降低开销。另外，HashSet的底层就是HashMap，借用了HashMap的方法。
