HashMap源码学习

HashMap是Map的实现类
Map与Collection一样是一个顶级容器接口
HashMap中存放一对泛型
Set key 和 Map Value
Map也称映射表 键值对映射
通过键找到值

Map方法

int size()

map的大小
有多少个键值对

boolean isEmpty()

判断是否有键值对

boolean containsKey(Object key)

是否包含键

boolean containsValue(Object value)

是否包含值

V get(Object key)

得到键的值

V put(K key, V value)

放入键值对

V remove(Object key)

删除key的键值对

void putAll(Map<? extends K, ? extends V> m)

放入其他map中的键值对

void clear()

清除所有键值对

interface Entry<K,V>

内部接口
map中一个键值对的方法

HashMap遍历方式

纵切遍历

public class Main {
public static void main(String[] args) {
HashMap<String,String> map=new HashMap<>();
map.put("nihao","90");
map.put("lall","98");
map.put("aa","asf");
map.put("asds","sadsad");
Set<string>keys= map.keySet();
for (String key:keys){
System.out.println(key+":"+map.get(key));
}
}
}</string>

横切遍历

public class Main {
public static void main(String[] args) {
HashMap<String,String> map=new HashMap<>();
map.put("nihao","90");
map.put("lall","98");
map.put("aa","asf");
map.put("asds","sadsad");
Set<Map.Entry<String,String>> entrySets = map.entrySet();
for (Map.Entry<String,String> node: entrySets){
System.out.println(node.getKey()+" "+node.getValue());
}
}
}

HashSet

extends AbstractSet<e>
implements Set<e>, Cloneable, java.io.Serializable
由Hashmap实现 由hashmap的key构成</e></e>

private transient HashMap<E,Object> map;

表示hashset是由hashset由hashmap实现

public boolean add(E e)

public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
可以看到 add是添加 hashmap

HashMap参数源码

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
初始化默认容量 底层有数组
aka as know all 周所周知 16

static final int MAXIMUM_CAPACITY = 1 << 30;

最大容量 为2的30次方

static final float DEFAULT_LOAD_FACTOR = 0.75f;

默认加载因子
当放入的值达到原容量的0.75倍时进行扩容
也就是当数量达到12时进行扩容
每次扩容为原来2倍
ArrayList只有放超过容量时才增长
并且ArrayList没有默认加载因子
0.75倍时 rehash过程会快

static final int TREEIFY_THRESHOLD = 8

hashmap进行树化的值 为8

static final int MIN_TREEIFY_CAPACITY = 64;

树化 最小容量为64

transient Node<K,V>[] table;

Node结点数组
hash列表

transient int size;

记录hashMap大小

transient int modCount

fali-fast的统计值

int threshold

转换因子
树化使用

final float loadFactor

加载因子
用来扩容

public HashMap(int initialCapacity, float loadFactor)

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;
this.threshold = tableSizeFor(initialCapacity);
}
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;
this.threshold = tableSizeFor(initialCapacity);
}
initialCapacity初始化大小
初始化大小小于零-异常
初始化大于最大容量-初始化大小等于最大容量
加载因子小于零 --异常
加载因子赋值
把初始化大小算入加载因子

内部类

static class Node<K,V> implements Map.Entry<K,V>

最小的hashmap默认结点
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;

Node(int hash, K key, V value, Node<K,V> next) {
    this.hash = hash;
    this.key = key;
    this.value = value;
    this.next = next;
}

public final K getKey()        { return key; }
public final V getValue()      { return value; }
public final String toString() { return key + "=" + value; }

public final int hashCode() {
    return Objects.hashCode(key) ^ Objects.hashCode(value);
}

public final V setValue(V newValue) {
    V oldValue = value;
    value = newValue;
    return oldValue;
}

public final boolean equals(Object o) {
    if (o == this)
        return true;
    if (o instanceof Map.Entry) {
        Map.Entry<?,?> e = (Map.Entry<?,?>)o;
        if (Objects.equals(key, e.getKey()) &&
            Objects.equals(value, e.getValue()))
            return true;
    }
    return false;
}

}
1.参数有key value hash 和next指针
2.其中key和value为存储的值
3.node中的hash值是重新计算的
4.key不能再改变 ;value可以改变具有setvalue内部方法
5.equals方法:先判断 o==this内存地址相同表示是同一个 ,再判断是否entry ,再判断key和value的值是否相同

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V>

树节点 当数组长度大于64且链表长度大于8时将默认结点转化为树结点

  • final TreeNode<K,V> root()

    根节点方法

  • static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root)

    移动树结点

  • final TreeNode<K,V> find(int h, Object k, Class<?> kc)

    查找树结点方法

  • final TreeNode<K,V> getTreeNode(int h, Object k)

    获得树结点的方法

  • static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root)

    TreeNode在增加或删除节点后,都需要对整个树重新进行平衡,平衡之后的根节点也许就会发生变化,此时为了保证:如果HashMap元素数组根据下标取得的元素是一个TreeNode类型,那么这个TreeNode节点一定要是这颗树的根节点,同时也要是整个链表的首节点

  • static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,TreeNode<K,V> x)

    红黑树的平衡调整
    计算左右子树深度判断是否平衡
    红黑树是弱平衡的查找树

  • final void treeify(Node<K,V>[] tab)

    1.将treeifyBin传过来的双向链表进行树化操作、
    2.首先判断root结点将其变成root结点
    TreeNode<K,V> root = null;
    for (TreeNode<K,V> x = this, next; x != null; x = next) {

    next = (TreeNode<K,V>)x.next;
    x.left = x.right = null;
    if (root == null) {
        x.parent = null;
        x.red = false;
        root = x;
    }

    3.对结点的hash值进行大小判断
    如果两个节点的key的hash值相等,那么还要通过其他方式再进行比较
    如果当前链表节点的key实现了comparable接口,
    并且当前树节点和链表节点是相同Class的实例,
    那么通过comparable的方式再比较两者。
    如果还是相等,最后再通过tieBreakOrder比较一次
    对dir进行赋值
    K k = x.key;
    int h = x.hash;
    Class<?> kc = null;
    for (TreeNode<K,V> p = root;;) {

    int dir, ph;
    K pk = p.key;
    if ((ph = p.hash) > h)
        dir = -1;
    else if (ph < h)
        dir = 1;

    else if ((kc == null &&

          (kc = comparableClassFor(k)) == null) ||
         (dir = compareComparables(kc, k, pk)) == 0)
    dir = tieBreakOrder(k, pk);

    4.保存当前树节点
    TreeNode<K,V> xp = p;
    5.根据dir的值将树结点放入上个结点的左或右的位置
    if ((p = (dir <= 0) ? p.left : p.right) == null) {

    x.parent = xp;
    if (dir <= 0)
        xp.left = x;
    else
        xp.right = x;

    6.放入之后进行平衡调整
    root = balanceInsertion(root, x);
    break;

    7.由于红黑树平衡调整会变化根节点,但由于要基于树来查找,所以就应该把 tab[N] 得到的对象一定根节点对象,而目前只是链表的第一个节点对象,所以要做相应的处理。
    moveRootToFront(tab, root);

方法

static final int hash(Object key)

static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
1.hash计算方法
2.只使用key的值进行计算
3.hash确定放入的位置
4.如果hash为空则放入0位置如果不为空则key对象的hashCode与其hashCode无符号右移16位后的结果进行异或运算
(高位取反,低位与原来的高位异或)

static final int tableSizeFor(int cap)

static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
计算底层数组大小
先减一
进行或运算并逐渐无符号右移
如果结果不小于0则返回1否则如果不大于最大值n+1

public HashMap()

构造方法
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
赋值加载因子为默认加载因子值

public V put(K key, V value)

重写map的put方法
调用putVal方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value,boolean onlyIfAbsent, boolean evict)

1.此处hash的值是对key的hashCode值进行计算(无符号右移16位后,高位保留,低位是原来的高位和低位异或)后的hash值

2.如果成员数组容量为零的话,将重新计算后的数组容量赋值给n
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
3.在数组中15与hash如果为空则放入新元素
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
4.如果size的值大于threshold则执行resize进行扩容
if (++size > threshold)
resize();
5.如果key为同一个值,替换新的Value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
判断Value是否为空,替换value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
6.如果树化创建一个新的树结点
if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
7.当binCount(单个位置上的结点个数)为空时放入新的结点 如果binCount 大于等于7(TREEIFY_THRESHOLD为8源码先放入一个结点所以减一)时进树化链表判断
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
8.判断传入key值是否一致,一致则替换value值,不一致则重新p为赋值下一个
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
9.当size大于threshold时,进行resize()
重新设置数组大小

void afterNodeInsertion(boolean evict) { }

将来可能进行修改的方法,这里为空方法

final Node<K,V>[] resize()

1.重新计算数组大小的方法
2.创建新的hashmap时会通过此方法创建一个大小为16的数组和赋值转化因子
3.当oldCap不为零时newCap为oldCap的两倍(数组扩容一倍)
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
4.数组扩大后 进行rehash重新取余

  • rehash

    1.rehash为resize中对数组上的结点重新分配位置的过程
    2.如果旧数组位置上有值则将旧数组上的记录并将其赋值为空
    if (oldTab != null) {

    for (int j = 0; j < oldCap; ++j) {
        Node<K,V> e;
        if ((e = oldTab[j]) != null) {
            oldTab[j] = null;

    3.如果旧数组位置上有结点并且该交接点的next为空则将该结点重新取余运算放到新数组上
    if (e.next == null)

    newTab[e.hash & (newCap - 1)] = e;

    4.如果该结点为树结点,重新分配位置
    else if (e instanceof TreeNode)

    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

    5.如果为链表则重新分配位置
    如果结点的hash值与旧容量的结果为0时记录为lo链表不为零时记录为hi链表
    Node<K,V> loHead = null, loTail = null;
    Node<K,V> hiHead = null, hiTail = null;
    Node<K,V> next;
    do {

    next = e.next;
    if ((e.hash & oldCap) == 0) {
        if (loTail == null)
            loHead = e;
        else
            loTail.next = e;
        loTail = e;
    }
    else {
        if (hiTail == null)
            hiHead = e;
        else
            hiTail.next = e;
        hiTail = e;
    }

    6.将lo,hi链表最后一个结点的next赋值为空并且将lo链表放在新数组原标号位置上,将hi链表放在新数组原标号加就容量的位置上
    while ((e = next) != null);
    if (loTail != null) {

    loTail.next = null;
    newTab[j] = loHead;

    }
    if (hiTail != null) {

    hiTail.next = null;
    newTab[j + oldCap] = hiHead;

    }

构造方法

hashmap的构造方法,在hashmap中,我们知道底层的拉链数组是一个节点数组
节点为Node<K,V> 这个数组叫table (table 在外界看不到)
这个方式我们见过ArrayList里有一个elementData是一个Object[]
进入Node里,这个Node里,记录了一个key,一个Value和一个next没有prev所以Node可以变成链表,但不是双向链表(只有next域)
里面还有一个hash的值,这个是现算出来的,其和key相关但是不是key的hashcode值
我们通过put方法来看往一个空的hashmap里放入一个值的时候回发什么,首先用户调用put(K,V)对象执行put方法,其次对象执行putVal方法
进入putVal方法,因为table是空所以tab=resize();方法resize时会初始化table

final void treeifyBin(Node<K,V>[] tab, int hash)

1.在resize方法中如果链表结点大于8时则运行该方法
2.treeifyBin为判断树化的方法
3.如果数组为空或者数组长度小于MIN_TREEIFY_CAPACITY(64)时进行扩容
n赋值为数组长度
index赋值为hash对数组长度的取余结果
e为该数组一个位置上的头结点
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
4.当数组长度大于64时
如果结点不为空则将链表各个结点变成树结点形成双向链表
e逐渐赋值为链表中的后一个结点
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
5.变成双向链表后如果头结点不为空则将双向链表变成红黑树
if ((tab[index] = hd) != null)
hd.treeify(tab);

TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next)

将链表结点转化为树结点的方法

static Class<?> comparableClassFor(Object x)

只有当传入对象的运行时类型符合”class C implements Comparable”这个条件时,返回对象的运行时类型,否则返回null

static int compareComparables(Class<?> kc, Object k, Object x)

比较两个Object实体的大小
源码思路:
判断x是否等于null与x的class类型是否与给定的kc类类型一致,如果都满足则调用compareTo方法判断两个实体的大小是否相等

static int tieBreakOrder(Object a, Object b)

比较两个对象的大小,该方法返回值绝对不会等于0
使用对象本身的hashCode进行比较