参考
参考
参考Yikun
参考Java7 HashMap分析
参考CSDN
HashMap是一个散列链表，它由数组作为容器，每一个元素是一个链表。在创建HashMap的时候会根据默认的临界域创建一个长度是n的2次方的数组，因为元素的位置由hash和lenght共同决定
当length是n^2时，可以更好的减少碰撞。在插入元素时首先会遍历容器是否有相同的元素。如果有会覆盖之前的元素。如果没有在当前位置链表头结点放置新的元素，如果原先的位置有元素，那么新元素指向老的元素形成链表。在查找元素的时候会遍历数组中的每一个链表以及链表的子元素。找到对应的元素
一、基本参数
DEFAULT_INITIAL_CAPACITY：默认容量
DEFAULT_LOAD_FACTOR：默认的负载因子,表示散列链表的使用度，数越大那么使用度越高。
entry：链表对象
table：链表的容器是一个数组
threshold：临界点，当达到这个临界点的时候进行扩容，它等于负载因子*容量大小
二、创建一个HashMap
1.首先会判断初始容量的大小是否符合条件，不能太大也不能太小
2.创建一个Entry的数组
3.根据默认的临界点，计算一个最合适的容量尽量减少碰撞保证capacity(lenght)是n的次方。
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY) {
initialCapacity = MAXIMUM_CAPACITY;
} else if (initialCapacity < DEFAULT_INITIAL_CAPACITY) {
initialCapacity = DEFAULT_INITIAL_CAPACITY;
}
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// Android-Note: We always use the default load factor of 0.75f.
// This might appear wrong but it's just awkward design. We always call
// inflateTable() when table == EMPTY_TABLE. That method will take "threshold"
// to mean "capacity" and then replace it with the real threshold (i.e, multiplied with
// the load factor).
threshold = initialCapacity;
init();
}
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
//计算一个合理的容量 capacity是n的2次方
int capacity = roundUpToPowerOf2(toSize);
// Android-changed: Replace usage of Math.min() here because this method is
// called from the <clinit> of runtime, at which point the native libraries
// needed by Float.* might not be loaded.
float thresholdFloat = capacity * loadFactor;
if (thresholdFloat > MAXIMUM_CAPACITY + 1) {
thresholdFloat = MAXIMUM_CAPACITY + 1;
}
threshold = (int) thresholdFloat;
table = new HashMapEntry[capacity];
}
二、Entry
next：保存当前table位置 下一个entry元素
value：是值
二、put方法
1.如果是空健，创建一个空元素entry返回
2.如果不是空，那么根据key的length计算出index---在数组中存放的位置。
3.如果当前位置有元素，看for循环中HashMapEntry<K, V> e = tab[index]; e != null，那么判断它们的hash值，和健的值是否相等。如果相等新的值会覆盖旧的值，并且返回给客户端之前的值
4.如果table已经满了将当前的table扩大2倍。
5.如果没有覆盖新的元素，那么获取当前table位置链表的头结点，新的元素就放置在头结点的位置，并且它的next指向原来元素，如果原来这个位置上有元素，那么形成链表
- int index=hash & (table.length - 1)，这里的table.length==capacity==n^2。查看Java7的的资料 当table.length - 1=15和14时，length是16和15。16是4^2而15不是。所以在table.length-1=14时发生的碰撞情况很多。
注意修改了addEntry修改了table[index]的指向。
@Override public V put(K key, V value) {
if (key == null) {
如果是空健，那么创建一个entry对象
return putValueForNullKey(value);
}
计算hash值
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
int index = hash & (tab.length - 1);
//遍历数组中的元素
for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
//加入元素的key的hash值和数组中现有元素的key的hash值和内容相同，那么替换它
if (e.hash == hash && key.equals(e.key)) {
preModify(e);
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
modCount++;
addNewEntry(key, value, hash, index);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
三.get方法获取数据
1.首先如果key是空键，判断是否有对应的entry。如果有返回entry存储的值。
2.如果不是空值，根据hash算法以及数组长度计算出index
3.取出数组对应的index位置保存的entry，遍历这个entry（因为它是一个链表），一次循环后，循环值e=e.next(),再进行循环，当e的hash值和key的值相同时取出对应的值
public V get(Object key) {
if (key == null) {
HashMapEntry<K, V> e = entryForNullKey;
return e == null ? null : e.value;
}
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
e != null; e = e.next) {
K eKey = e.key;
if (eKey == key || (e.hash == hash && key.equals(eKey))) {
return e.value;
}
}
return null;
}
四、HashMap的查找
1.遍历数组中所有存储的entry，然后遍历该位置的链表，确认是否有元素
@Override public boolean containsValue(Object value) {
HashMapEntry[] tab = table;
int len = tab.length;
if (value == null) {
for (int i = 0; i < len; i++) {
for (HashMapEntry e = tab[i]; e != null; e = e.next) {
if (e.value == null) {
return true;
}
}
}
return entryForNullKey != null && entryForNullKey.value == null;
}
// value is non-null
for (int i = 0; i < len; i++) {
for (HashMapEntry e = tab[i]; e != null; e = e.next) {
if (value.equals(e.value)) {
return true;
}
}
}
return entryForNullKey != null && value.equals(entryForNullKey.value);
}
HashMap的优缺点
1.它的查找性能很高，根据Hash算法计算出key在整个table数组中的位置，遍历这个数组中的链表找到指定的元素，不需要去一个一个对比。
2.在插入时需要查询该位置是否有相同元素。如果发生hash碰撞会形成链表，所以它的插入效率没有数组高
3.它不是同步的，如果同时操作同一个HashMap会造成数据不一致。
