HashMap
HashMap是一个散列链表，用一个Entry数组存储所有的数据。Entry中有一个next引用，也就说Entry数组就是一个个单链表。put方法首先根据key计算hashCode，根据数组长度取模或者异或运算得到对应数组的下标，当hash值相同或者计算得到的下标相同时则往单链表追加数据。为了让数据均匀分布在每一条链上，数据量达到最大容量的0.75时就会扩容并重新计算每一个元素的hash,然后添加到新的数组中。
image.png
核心方法
public V put(K key, V value) {
//计算hash值
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//计算数组索引
if ((p = tab[i = (n - 1) & hash]) == null)
//该索引位置的元素为null则直接添加
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//查找是否已存在key相同的元素
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
//已存在相同key的元素则直接修改该值
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//访问回调
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//扩容
if (++size > threshold)
resize();
//插入回调
afterNodeInsertion(evict);
return null;
}
LinkedHashMap
LinkedHashMap 继承HashMap 他包含上面提到的HashMap的存储结构，而且它的Entry元素除了维护next引用，还会维护 before after引用形成双向链表。也就是套用Hashmap同时维护了一个单链表一个双向链表而且两者互不影响。
image.png
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
//调用put方法时回调此方法，维护双向链表的关系
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
Lru
一般使用LinkedHashMap可以实现Lru算法。
基于访问排序：每次使用get等访问一个元素就将该元素放到队尾，插入元素后如果
removeEldestEntry(first)返回true则删除队头元素
基于插入排序：总是队尾入队，子类复写removeEldestEntry(first)并做自己的逻辑判断返回true的时候会删除队头元素
//java.util.LinkedHashMap
//插入元素后父类HashMap会回调此方法
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
//调用父类删除元素的方法
removeNode(hash(key), key, null, false, true);
}
}
//访问元素后HashMap会回调此方法 将访问的元素放到双向链表的队尾
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
LruCache 示例
//org.apache.ibatis.cache.decorators.LruCache
public class LruCache implements Cache {
private final Cache delegate;
private Map<Object, Object> keyMap;
private Object eldestKey;
public LruCache(Cache delegate) {
this.delegate = delegate;
this.setSize(1024);
}
public String getId() {
return this.delegate.getId();
}
public int getSize() {
return this.delegate.getSize();
}
public void setSize(final int size) {
this.keyMap = new LinkedHashMap<Object, Object>(size, 0.75F, true) {
private static final long serialVersionUID = 4267176411845948333L;
protected boolean removeEldestEntry(Entry<Object, Object> eldest) {
boolean tooBig = this.size() > size;
if (tooBig) {
LruCache.this.eldestKey = eldest.getKey();
}
return tooBig;
}
};
}
}
手写一个HashMap
这个例子实现了HashMap最基本的功能，忽略了自动扩容的部分代码
package com.execlib;
public class MyHashMap<K,V> {
private Entry<K,V>[] ele;
private int size;
public MyHashMap(){
init();
}
private void init(){
ele = new Entry[20];
}
public V put(K key,V value){
int hashCode = key.hashCode();
int index = hashCode&(ele.length-1);
Entry<K,V> e = null;
for (e = ele[index];e!=null;e = e.next){
if (e.hash == key.hashCode()&&e.key.equals(key)){
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
size++;
addNewEntry(index,key,value,hashCode);
return value;
}
public void addNewEntry(int index,K key,V value,int hashCode){
ele[index] = new Entry<K, V>(key,value,ele[index],hashCode);
}
public V get(K key){
int hashCode = key.hashCode();
int index = hashCode&(ele.length-1);
Entry<K,V> e = null;
for (e = ele[index];e!=null;e = e.next){
if (e.hash == key.hashCode()&&e.key.equals(key)){
return e.value;
}
}
return null;
}
public V remove(K key){
int hashCode = key.hashCode();
int index = hashCode&(ele.length-1);
Entry<K,V> e = null;
Entry<K,V> pre = null;
for (e = ele[index];e!=null;pre = e,e = e.next){
if (e.hash == key.hashCode()&&e.key.equals(key)){
if (pre==null){
ele[index] = null;
}else {
pre.next = e.next;
}
size--;
}
}
if (e == null)
return null;
return e.value;
}
public int getSize() {
return size;
}
public class Entry<K,V>{
public Entry(K key, V value, Entry next, int hash) {
this.key = key;
this.value = value;
this.next = next;
this.hash = hash;
}
private K key;
private V value;
private Entry next;
private int hash;
}
}
测试代码
package com.execlib;
public class TestMyHashMap {
public static void main(String[] args) {
MyHashMap<Integer, Integer> myHashMap = new MyHashMap<Integer, Integer>();
for (int i = 0; i < 1000; i++) {
myHashMap.put(i,i);
}
for (int i = 0; i < 10022; i++) {
myHashMap.get(i);
myHashMap.remove(i);
}
System.out.println(myHashMap.getSize());
}
}
image.png
网友评论