JAVA容器

  2020-5-29 


容器相关源码阅读笔记 ,未完待续

线程安全

在拥有共享数据的多条线程并行执行的程序中,线程安全的代码会通过同步机制保证各个线程都可以正常且正确的执行,不会出现数据污染,无法运行,死循环等意外情况

上面举例了hashmap为什么线程不安全(两个原因)

而其它容器,比如arraylist也是线程不安全的:https://www.cnblogs.com/maoyali/p/8805975.html是因为**无法保证add等操作的原子性,导致数组越界等问题。**(比如add要先判断容器空间是否足够,和hashmap的b原因一样)

Hashmap

hashmap详解

源码解析【】:https://www.jianshu.com/p/4aa3bb16f36c

https://my.oschina.net/muziH/blog/1596801

①hashmap通过hashcode()找到目标在数组中的存储位置(),再根据equals()方法从该位置上的链表中取出目标【用hashcode算出目标在散列表哪个位置,通过equals在该位置的链表(红黑树)上一一进行比较,hashcode相同也就是hash冲突,所以要串在后面的链表/红黑树上】插入的时候,就是插入在散列表对应位置的链表/红黑树里(链表的话,串在最后一位后面)

默认的equals方法比较自定义的对象比较的是地址,hashcode也是默认将对象的地址拿去hash,所以要将自定义对象加入hashmap的时候是要用hashcode和equals来判断对象是否相等的,这个时候就要想清楚了要不要重写hashcode和equals(不重写,那hashmap判定两个对象是否相等就是地址相等才叫相等)

P.S.使用==,eqauls比较两个自定义对象默认比较地址(==不可重写,eqauls可重写)

③注意:hashcode()和equals()都是Object对象的方法(hashmap只是使用了要hash的Object的这两个方法)。且,重写了eqalus()就必须重写hashcode()(因为是先判断hashcode(),再判断eqauls())

重写示例:

class Key {
    private Integer id;

    public Integer getId() {
        return id;
    }

    public Key(Integer id) {
        this.id = id;
    }

    @Override
    //这里我让hashCode方法返回该对象内部的变量id的hashCode,也就是说,你hashmap在hash我这个对象的时候,实际上是hash的变量id!而不是默认的这个对象的地址
    public int hashCode() {
        return id.hashCode();
    }

    @Override
    //这里就是比较本对象与传入对象是否相等的具体方法了(hashcode可能导致冲突,不够,还得equals定义具体的比较方法)
    public boolean equals(Object obj) {
        if (obj == null || !(obj instanceof Key)) {
            return false;
        } else {
            return this.getId().equals(((Key) obj).getId());
        }
    }
}

④hashmap的rehash

当散列表(list)被填的越满,冲突概率越高,当超过一个负载因子后,就会resize。resize开销很大,扩大一倍,需要重新计算hash。

hashmap可以使用HashMap(int initialCapacity, float loadFactor)来指定初始容量和负载因子,根据自己的需求设置

hashmap默认初始容量为16,默认负载因子为0.75

hashmap长度必须为2的幂(为了hash均匀,hashcode/长度映射到hash表里,这个长度-1最好是全1,(0开始)也就是1000就ok,也就是2的幂次)

线程不安全

a. 但rehash会遇到问题——线程不安全多个线程同时对hashmap进行rehash扩容的时候,存储在链表中的元素的次序会反过来(transfer函数转移的时候是逆序转移的,比如1->2->3 rehash到新链表就成了3->2->1)。【所以如果条件竞争发生了,rehash就会产生环形链表,那么就死循环】

https://www.cnblogs.com/laojiao/p/9622058.html

b.另一方面,如果多个线程同时put数据到同一个位置,会导致某线程put的数据被立即覆盖(线程1判断该位置没有后打算put了,但被线程2给插入了,也就是【无法保证put等操作的原子性】,数据不一致)

【因为如此,才引入了ConcurrentHashMap,其是线程安全的】(ConcurrentHashMap替代hashtable,hashtable也是线程安全的,但它是全表加锁,而前者锁细化,所以效果好)

⑥hashmap在链表长度超过8的时候会转为红黑树

随机哈希代码下,桶中的节点频率遵循泊松分布,超过8的概率很小(基于概率统计得出

https://blog.csdn.net/fst438060684/article/details/89716554

ArrayList

hashset 加速比较的办法

同hash join

比如要在list a中找list b共有的元素

可以将list b全部求hash到一个set中

然后遍历list a,求hash(a)判断a是否在set中

hashmap计数的思想!特别是对于重复元素,hashmap非常有效

StringBuider、StringBuffer区别(无关)

StringBuffer是线程安全的,所以使用效率比stringbuilder低一些
StringBuilder是单线程的,不提供同步


且听风吟