简介

hashmap基于哈希表的底层map实现。
哈希表控制键。
数组+链表 链表>8,数组长度大于64 数组大于64转为红黑树，O(n）变为O(log n),小于6从红黑树转为链表。
数组小于64，链表>8,不转红黑树，先扩容（重新计算哈希值，将原map内数据重新计算哈希值存放）
存取无序
k,v可以为null，key唯一，只能有一个null
继承abstract map,实现map，cloneable,Serializable

数据结构是存储数据的方式。

1.创建hashmap，构造方法中创建一个长度16的Entry[] table 用来存放键值对数据。
jdk1.8后不在构造方法中创造，在第一次put时创建Node（实现Map.Entry）[] table
2.存储数据，调用key的hashcode然后结合数组长度采用某种算法计算索引值。
若索引没数据，直接存。

哈希表底层采用什么算法计算哈希值
key.hashcode方法的值结合无符号右移（>>>），按位异或（^），按位与(&)计算索引
平方去中法，取余法，伪随机数法。取余效率低，位运算效率高。
存储数据计算的索引值的桶中有数据时，先看key的hash值是否相等，哈希值不相等，划出节点存储数据。
哈希值相同，发生哈希碰撞，判断key内容是否相等（==||equals），相等替换v，不相等循环链表(或者红黑树)比较key，都不相等直接存储。

扩容：超过阈值，扩容两倍

threshold临界值=容量*加载因子

成员变量

• private static final long serialVersionUID = 362498820763181265L; 序列化版本号
• static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
  集合的初始化容量,必须是2的次幂
  为了减少哈希碰撞，充分数组空间
  计算索引实际上是取模 hash%length 效率不高，源码优化为 hash&(length-1)
  数组长度为2^n时，length-1 为 011111，按位与运算都为1则为1，否则为0减少哈希碰撞。非2^n时极其容易发生哈希碰撞。hash冲突越大，数组链表越长，hashmap效率越低。

一般会通过%确定位置，但是性能不如&运算，在n=2^n时，hash&(length-1)==hash%length

构造函数给容量为10会变成16 最近的2的n次幂

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;
}
1
2
3
4
5
6
7
8
9

-1是为了避免传16容量变为32的情况。
右移16位，最高就是32个1，在进入前进行了判断大于最大值2的30次方，就用最大值，
此时移位为最大30个1，不会大于等于2的30次，加1后得到2的30次

• static final float DEFAULT_LOAD_FACTOR = 0.75f; 加载因子

• 为什么在链表长度大于8时变为红黑树
  树节点是常规节点的两倍，包含足够多的节点才会转变为红黑树。
  正常情况下，hashcode算法bin节点的频率会遵循泊松分布。一个bin中链表长度达到8个元素的概率为0.0000006，几乎不可能。
  log2 (8)=3 n/2=4

• static final int UNTREEIFY_THRESHOLD = 6; 节点数小于6转换为链表

• static final int MIN_TREEIFY_CAPACITY = 64; 数组大于64才会转为红黑树，否则扩容。

• transient int size; 存放元素的个数

• transient int modCount; 扩容或者更改map的计数器

• int threshold 临界值

• final float loadFactory 加载因子 越接近1说明存储越多，接近0说明越稀疏
  size/capacity
  尽量减少扩容次数。

成员方法

构造方法

无参构造 赋值默认加载因子
指定容量 赋值默认加载因子，计算阈值
指定容量和加载因子 计算阈值，赋值形参加载因子
形参map 循环放到hashmap中
putMapEntries
float ft = ((float)s / loadFactor) + 1.0F;
加1是为了减少扩容

treeifBin

链表大于8，数组长度小于64，扩容
数组长度大于64，循环链表建立红黑树，然后旋转至平衡

扩容方法 resize

超过容量*加载因子，扩容为2倍
删除节点个数小于6个变为链表，因为小于6链表遍历比红黑树更快

扩容是rehash都是翻倍，和原结果比多个bit位，要么在原来位置（高位0），要么被分配到 原位置+旧容量（高位1） 这个位置 均匀的将之前冲突的节点分配到新的桶中。

如果只有一个元素，直接存。树节点拆分，遍历链表。

putval方法

索引计算过程
(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
i = (table.length - 1) & hash
等同于对数组长度取余

hashcode高位变化很大，低位变化很少或没有变化时，直接与操作会很容易哈希碰撞。

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;//先判断hashmap数组是否为空，为空则创建数组
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);//根据索引值找到对应桶为空，则插入新节点到桶
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;//头节点不为空，并且哈希值和key值相等则进行覆盖
            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);//插入后链表大于8，转化为红黑树，这个方法会判断数组长度，数组长度小于64时，先扩容
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;//次节点的hash值和key相等，跳出循环
                    p = e;//下个节点不为空，hash和key不相等，将p.next赋值给p，继续魂环
                }
            }
            if (e != null) { // p.next不为空时
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)//onlyIfAbsent 为true代表key相同，不修改value的值，putval中穿的false
                    e.value = value;//进行值的覆盖
                afterNodeAccess(e);//将当前节点挪到最后
                return oldValue;
            }
        }
        ++modCount;//修改计数器
        if (++size > threshold)
            resize();//添加元素后超过阈值扩容
        afterNodeInsertion(evict);
        return null;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

删除方法

计算哈希值，获取索引得到桶的位置，比较key是否相等，相等删除，不相等红黑树根据hash和key获取节点，链表循环到key相等的节点进行删除。

get方法

计算哈希，获取桶位置，是不是第一个元素，是返回，否则遍历红黑树（因为添加时保证有序因此查找使用折半查找）或者链表比较key值，相等返回

遍历方式

{
    public static void main(String[] args) {
        HashMap<String,Integer> map =new HashMap();
        map.put("1",1);
        map.put("2",2);
        map.put("3",3);
        map.put("4",4);

//        method(map);
//        method1(map);
//        method2(map);
        method3(map);

    }
//jdk8以后使用map中的默认方法
    private static void method3(HashMap<String, Integer> map) {
        map.forEach((key,value)->{
            System.out.println(key+"---"+value);
        });
    }

    //通过get方式   不建议，两次循环
    private static void method2(HashMap<String, Integer> map) {
        Set<String> keys=map.keySet();
        for(String key:keys){
            Integer v=map.get(key);
            System.out.println(key+"----"+v);
        }
    }

    //迭代器迭代
    private static void method1(HashMap<String, Integer> map) {
        Set<Map.Entry<String,Integer>> entries =map.entrySet();
        for (Iterator<Map.Entry<String,Integer>> it=entries.iterator();it.hasNext();){
            Map.Entry<String,Integer> entry=it.next();
            System.out.println(entry.getKey()+"-----"+entry.getValue());
        }
    }
//分别遍历key和value
    private static void method(HashMap map) {
        Set<String> keys=map.keySet();
        for (String key:keys){
            System.out.print("  key  "+key);
        }
        Collection<Integer> values=map.values();
        System.out.println("");
        for(Integer value : values){
            System.out.print("  value  "+ value);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

使用技巧

确定个数，创建hashmap
存7，生成8，第6个就扩容。
初始化容量为 元素个数/初始化因子 +1，减少扩容概率
float ft = ((float)s / loadFactor) + 1.0F;
7/0.75+1=10 创建后为16