`HashCode`

HashCode()，在未被重写前，即object类中，是一个Native方法，默认返回JVM生成的随机数，是一个独特值，可以看作是对象的身份ID

而在String类中，HashCode被重写

public int hashCode() {
       int h = hash;
       if (h == 0 && value.length > 0) {
           char val[] = value;

           for (int i = 0; i < value.length; i++) {
               h = 31 * h + val[i];
           }
           hash = h;
       }
       return h;
   }

为什么使用31作为乘数？？？

31是一个不大不小的奇质数，如果选择偶数计算，会导致乘积运算时的数据溢出。如果选择一个很小的数，那么hashcode会分布在一个很小的范围内，容易造成哈希值的冲突；如果选择一个很大的数，那么可能会超出整型变量的范围。
在二进制中31等于2<<5-1，那么31*i即为（i<<5）-i，这种乘积运算可以直接通过位移来提升性能，JVM也支持这种优化方式
不止31，33，37，39，41也可以作为乘数，当我们使用超过50,000个单词来计算hashcode，这5个乘数都得到的哈希值冲突都小于7，31最小。同时hash的目的就是让数据尽可能分散排布，而以31作为乘数得到的结果分布最为均匀。

HashMap如何计算索引值

第一步：计算hash

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//将key的hashCode值 与 key的hashCode值的高16位(无符号右移)，进行^异或运算，得到一个hash值

原理：引入扰动函数

扰动函数就是为了增大随机性，减少碰撞，在引入扰动函数后散列表的数据分布更加均匀

第二步：计算索引

1 2	`//n为数组长度从 index = hash & (n-1);`

一般的散列算法是以取余%来计算散列值的，但是CPU在做 /除或 %取余运算时，效率是很低的。

所以使用位运算与，可以实现相同的结果，而且效率更高。

HashMap的容量

HashMap的初始化容量通常设置为2的幂次方大小，未指定大小时默认初始化为16，

这与hash & (n-1)密切相关，2次幂大小的数与运算与取余运算的效果相同

要减一，即n-1，我们才能获得一个01111这样的值（在和hash进行与运算的时候才可以获得范围合法的索引）

若指定一个奇数作为capacity，就会调用tableSizeFor()

若传入17，向正方向寻找一个最接近17的2的幂次方，即为32

通过位移运算+或运算将17的每一位都改为1，然后再加1，最后就可以得到32

扩容

1 2	`//负载因子 static final float DEFAULT_LOAD_FACTOR = 0.75f;`

负载因子就是一个阈值，当数据量超过这个阈值后，便要进行扩容

因为hashcode的特性，一个散列表地址可能对应多个元素，所以即使元素数量大于散列表地址数量，也可能出现无法把散列表占满的情况，在这种情况下，某些位置会出现碰撞，这降低了HashMap的性能

所以当散列表的位置使用到一定程度时，就需要进行扩容，默认0.75，也就是当使用3/4后，就进行扩容

为什么扩容时会直接乘以2：

以2倍扩容的方式扩容，元素在新表中的位置要么不动，要么原脚标位+扩容长度（二的幂次方偏移量），这样会使扩容的效率大大提高（JDK1.8后扩容不用重新rehash）
可以使元素均匀的散布hashmap中，减少hash碰撞

转换红黑树的条件

链表长度大于8
Entry数组大于64

HashCode()和equals()的关系，如何使用？

equals()来自Object()类，默认使用==来比较地址值，判断引用指向是否是一个对象。通过重写该方法来定义新的规则，比如String类中的equals方法就是逐个比较字符串的字符
HashCode()来自Object()类，这是一个本地方法，在没有被重写时默认返回对象在堆内存上的独特值，可以认为是对象在堆内存中的身份证号，具有唯一性。重写HashCode后，可以返回计算而出的哈希值，即散列算法，用于确定元素的桶位置，例如HashMap
如何使用：查找一个元素，当调用散列算法后，快速定位到相应位置，若该桶内有元素，则调用equals()，由于哈希碰撞的存在，HashCode()相等时，不一定就是相应的元素，所以必须调用equals()来判断是否为要查找的元素

==和equals的区别

==：若比较的是基本数据类型，则比较的是数值是否相等；如果比较的是引用数据类型，则比较的是地址值

equals()：用来比较引用指向的对象地址是否相等。不可用于基本数据类型的比较。

在Object类中，equals就是由==来实现的，可以认为equals在被重写前，两者作用是相等的

为何重写equals后一定要重写hashcode?

根据hashcode的规则，两个对象相等其哈希值一定相等

所以当重写equals后比如在String类中，两个字面量相同的字符串对象equals后一定返回true

但是如果不重写hashcode，默认返回JVM生成的独特值，此时两个对象的hashcode可能不会相等，与上文说的规则相矛盾。所以必须重写hashcode来符合这个规则

HashMap为什么是线程不安全的

JDK1.7可能造成死循环：由于resize时的数据迁移采用头插法（当时的人觉得比较高效），而头插法会导致链表顺序颠倒（因为先插入的元素在后面），当线程A未完成transfer操作时被挂起，而线程B成功完成了transfer操作，线程A再次获取时间片后继续执行transfer，由于头插法导致链表顺序颠倒，便有可能导致生成环形链表。
JDK1.8可能造成数据丢失：假设两个线程A、B都在进行put操作，并且hash函数计算出的插入下标是相同的，当线程A执行过程中由于时间片耗尽导致被挂起，而线程B得到时间片后在该下标处插入了元素，完成了正常的插入，然后线程A获得时间片，由于之前已经进行了hash碰撞的判断，所有此时不会再进行判断，而是直接进行插入，这就导致了线程B插入的数据被线程A覆盖了，从而线程不安全。

HashMap如何保证线程安全

Collections.synchronizedMap()方法传入HashMap的引用变量，返回一个新的Map，这个新的Map就是线程安全的，返回的并不是HashMap，而是map的一种实现。该方法封装了所有不安全的HashMap方法，使用了synchronized方法来进行互斥，和HashTable差不多，该方法使用代理模式new了一个新的类，这个类实现了Map接口。该方法的优点：实现简单；缺点：加锁的粒度较大，性能比较差。被synchronizedMap()包裹的map是可以传入null 键的。而concurrentHashmap不可以。
使用ConcurrentHashMap，使用了新的锁机制，把hashmap拆分成了多个独立的块，这样在高并发的情况下减少了锁冲突的可能。使用的是NonfairSync，这个特性调用CAS指令来保证原子性和互斥性。如果多个线程恰好操作到同一个segment，只有一个线程得到运行。优点：互斥的代码段小，性能更好，发生锁碰撞的几率低。缺点：代码繁琐。

ConcurrenHashMap和HashTable

HashTable它的每一个方法都是使用了synchronized同步锁机制，将整个入口锁起来，在多线程的情况下，他整个数组结构的入口就只能一条线程执行完成之后其他线程才能进入，无论下标是否相同，是否存在hash碰撞。

而ConcurrenHashMap由JDK1.5引入，降低了锁粒度且保证了线程安全

HashEntry内的成员变量value等都是volatile类型的，这样就保证别的线程对value值的修改，get方法可以马上看到

在JDK1.7之前，在初始化ConcurrentHashMap的时候，会初始化一个Segment数组,容量为16，Segment内部有一个table数组，存储entry数组+链表的结构

每个Segment都继承了ReentrantLock类，也就是说每个Segment类本身就是一个锁，使用了分段锁的机制，降低了锁粒度。

在查找时，定位segment和定位table后，依次扫描这个table元素下的的链表，要么找到元素，要么返回null。

在JDK1.8之后，引入红黑树且取消了segment设计。使用synchronize关键字，为每一个node对象加同步锁，将锁的粒度将到最低。

TreeMap和HashMap

为什么HashMap是无序的？

在对HashMap元素进行遍历的时候，是以数组下标为顺序，若该slot下存在链表和红黑树，则向下遍历，直到遍历完该slot下的所有元素。

众所周知，出现哈希冲突而存放在链表中的元素是不会按照顺序排放的，所以HashMap无序。

而TreeMap 的底层数据结构是一棵红黑树，红黑树上的元素都是有顺序的

TreeMap如何实现排序？

当使用无参构造时TreeMap treeMap = new TreeMap();，默认是升序的

但是TreeMap的构造方法可以传入一个Comparator对象，重写其中的Compare方法就可以定于以何种规则排序key

//按照key字母顺序排序
TreeMap<String,Integer> treeMap = new TreeMap<String,Integer>(new Comparator() {
            public int compare(Object o1, Object o2) {
                return ((String)o1).compareTo((String)o2);
            }
});
//Compare方法的原理：返回-1，无需交换元素，返回1，交换元素

HashMap：适用于Map插入，删除，定位元素；

TreeMap：适用于按自然顺序或自定义顺序遍历键（key）,性能不如HashMap

LinkedHashMap和HashMap

linkedHashmap

简单的说，LinkedHashMap其实就是在HashMap的基础上再维护了一个双向链表，来保持顺序性

这个顺序默认是插入顺序，可以将其看作是实现hashmap查找效率的链表

可以通过设置accessOrder设置为访问顺序

accessOrder默认为false，当设置为true时，会在每次get或put后将元素移动至双向链表尾部（LRU）

//使用linkedHashMap模拟实现LRU
class LRUCache {
    int cap;
    LinkedHashMap<Integer,Integer> cache = new LinkedHashMap<>();
    public LRUCache(int capacity) {
        this.cap = capacity;
    }
    //加入链表尾部
    void makeRecently(int key){
        int val = cache.get(key);
        cache.remove(key);
        cache.put(key,val);
    }
    public int get(int key) {
        if(!cache.containsKey(key)) return -1;
        makeRecently(key);
        return cache.get(key);
    }
    
    public void put(int key, int value) {
        if(cache.containsKey(key)){
            cache.put(key,value);
            makeRecently(key);
            return;
        }
        if(cache.size() >= this.cap){
            //找到链表头部的key,就是最久未使用的key,调用一次next()就是第一个元素
            int toBeRemoved = cache.keySet().iterator().next();
            cache.remove(toBeRemoved);
        }
        cache.put(key,value);
    }
}

#Java基础知识

HashMap

http://example.com/post/HashMap.html

作者

SamuelZhou

发布于

2022年10月30日

许可协议

计算机网络上一篇

买股票问题下一篇