HashMap的存储原理

import java.util.HashMap;

/**
*
* 创建对象HashMap<String,String> map = new HashMap<String ,String>();
*
* static final int DEFAULT_INITIAL_CAPACITY = 16;
* static final float DEFAULT_LOAD_FACTOR = 0.75f;
* public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
this(16,0.75f)
}
默认哈希表主数组的长度是16，默认的加载因子是0.75f

transient Entry<K,V>[] table;
public HashMap(int initialCapacity, float loadFactor) {
//给装填因子赋值 0.75f
this.loadFactor = loadFactor;
// threshold = 16*0.75=12 门槛值
threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
//table就是主数组的引用，创建了一个主数组长度是16的哈希表
table = new Entry[capacity];
}

*
* 添加键值对map.put("cn", "China");
*
* public V put(K key, V value) { cn China
* //如果key是空，进行特殊的处理
if (key == null)
return putForNullKey(value);
//计算key的哈希码，进行了二次散列，目的为了保证不同key的哈希码尽量不同，更分散更高效
int hash = hash(key);
//调用函数得到存储位置
int i = indexFor(hash, table.length);
//将元素添加到指定的位置
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//找到了现在要添加到关键字 ，新value替换旧的value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;//America替换了the United States
e.recordAccess(this);
return oldValue;
}
}

modCount++;
//如果没有找到，就创建一个新的节点并加入到链表中
addEntry(hash, key, value, i);
return null;
}
*
* final int hash(Object k) {
int h = 0;
if (useAltHashing) {
if (k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h = hashSeed;
}

h ^= k.hashCode();

h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}

*
* static int indexFor(int h, int length) {
return h & (length-1);
//采用位运算，效率更高结果等同于下一条语句
return h%length; h%16;//0--15
}



void addEntry(int hash, K key, V value, int bucketIndex) {
//如果达到了门槛值，就扩容 12>=12
if ((size >= threshold) && (null != table[bucketIndex])) {
//一次扩容1倍 16 32 64
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
//创建新的结点并加入
createEntry(hash, key, value, bucketIndex);
}

* 根据key获取值map.get("cn")
*
*
* public V get(Object key) {
* //如果关键字是null，特殊处理
if (key == null)
return getForNullKey();
//根据key找到对应的Entry，Entry就是一个存储了key-value的哈希表的链表节点
Entry<K,V> entry = getEntry(key);
//
return null == entry ? null : entry.getValue();
}
*
* 哈希表中一个链表节点的结构，[在JDK1.8中变成了Node]
* static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
}
*
* final Entry<K,V> getEntry(Object key) {
* //二次哈希，得到哈希码
int hash = (key == null) ? 0 : hash(key);
//根据哈希码得到存储的位置
int i= indexFor(hash, table.length)；
//在哈希表中查找指定key的Entry
for (Entry<K,V> e = table[i];
e != null;
e = e.next) {
Object k;
//找到了就返回
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
//如果没有找到，返回null
return null;
}
* @author Administrator
*
*/
public class TestHashMap {

public static void main(String[] args) {
HashMap<String,String> map = new HashMap<String ,String>();

map.put("cn", "China");

map.put("us", "the United States");

map.put("us", "America");


System.out.println(map.get("cn"));


}
}