简介
hashmap是双链表格式的存储结构<K,V>存储数据，没有顺序性，1.7基于hash表存储。允许空值存在，键中有且只允许有一个，值中也允许有空值存在。初始容量大小为16加载因子为0.75。
线程不安全，在并操作时存在安全问题。
常见操作解读
初始化new
初始化的时候无参情况下，使用默认初始大小和加载因子进行初始化。
//空参构造方法
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
//构造方法
//执行构造方法之前会加载类中的变量
//初始化一个Entry对象数组
//transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
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 V put(K key, V value) {
//是否为空Entry<K,V> table
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//key为null，hashMap专门空值设置一个存储方法
if (key == null)
return putForNullKey(value);
//计算hash
int hash = hash(key);
//计算index，根绝key的hash和table的长度
int i = indexFor(hash, table.length);
//是否有重复的key值，通过获取现有的table[i]是否为空来判断
//当不同key的hash值相同时为hash冲突，hash冲突时，需要便利所有的Entry比较是否key的==和equal方法一致。
//hash一致后Entry变为为链状，同一个index下有多个Entry[]数据，并把添加放置到重复index下的Entry中的最后一个
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
//重复key值处理
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++;
//添加Entry
addEntry(hash, key, value, i);
return null;
}
addEntry方法
void addEntry(int hash, K key, V value, int bucketIndex) {
//当前entry的size大小大于threshold（size*0.75加载因子）并且当前表的index值已经存在
//散列表散列值计算，通常是两种方法：链表法和开放地址法
//链表法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位；开放地址法是通过一个探测算法，当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位。
//1.7hashMap使用的就是链表法
if ((size >= threshold) && (null != table[bucketIndex])) {
//当大小超过threshold并且出现hash冲突的时候会扩容在不大于最大值的情况下是是旧表的二倍
resize(2 * table.length);
//是否重新计算hash
hash = (null != key) ? hash(key) : 0;
//给冲突的hash集合新表的长度再次计算hash
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
resize方法
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, initHashSeedAsNeeded(newCapacity));
table = newTable;
//重新计算 阀值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
threshold方法
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
//遍历旧表对迁移新表
for (Entry<K,V> e : table) {
//在对Entry链表的复制过程中可能会存在环的问题。多条线程并发操作，遍历Enrt表的时候会导致环的存在，新链表插入相比较旧链表而言是倒叙，因为多线程快慢问题可能导致。
//对有bucket链进行便利
while(null != e) {
//记录旧表的下一个entry值
Entry<K,V> next = e.next;
//是否重新计算hash
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
//计算idex值
int i = indexFor(e.hash, newCapacity);
//新表的指针反转旧表指向
e.next = newTable[i];
//旧的enry携带新的指向赋值给新的槽位
newTable[i] = e;
//旧表指针往下
e = next;
}
}
}
获取
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
getEntry方法
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
//hash重复的情况
//比较key的equals和==的方法
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;
}
删除
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
removeEnryForKey方法
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
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;
//hash相同时
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;
}