时间戳

首页 > 技术文章 > Java HashMap问题

Java HashMap问题

jiezai 2019-08-01 21:42 原文

   1：map集合简述：    

        我们常用的集合实现类有HashMap、LinkedHashMap、TreeMap，HashTable。HashMap根据key的hashCode值来保存value，需要注意的是，HashMap不保证遍历的顺序和插入的顺序是一致的。HashMap允许有一条记录的key为null，但是对值是否为null不做要求。
         
        HashTable类是线程安全的，它使用synchronize来做线程安全，全局只有一把锁，在线程竞争比较激烈的情况下hashtable的效率是比较低下的。因为当一个线程访问hashtable的同步方法时，其他线程再次尝试访问的时候，会进入阻塞或者轮询状态，比如当线程1使用put进行元素添加的时候，线程2不但不能使用put来添加元素，而且不能使用get获取元素。所以，竞争会越来越激烈。相比之下，ConcurrentHashMap使用了分段锁技术来提高了并发度，不在同一段的数据互相不影响，多个线程对多个不同的段的操作是不会相互影响的。每个段使用一把锁。所以在需要线程安全的业务场景下，推荐使用ConcurrentHashMap，而HashTable不建议在新的代码中使用，如果需要线程安全，则使用ConcurrentHashMap，否则使用HashMap就足够
　　　
        LinkedHashMap属于HashMap的子类，与HashMap的区别在于LinkedHashMap保存了记录插入的顺序。TreeMap实现了SortedMap接口，TreeMap有能力对插入的记录根据key排序，默认按照升序排序，也可以自定义比较强，在使用TreeMap的时候，key应当实现Comparable接口。
可以看到HashMap继承自父类（AbstractMap），实现了Map、Cloneable、Serializable接口。其中，Map接口定义了一组通用的操作；Cloneable接口则表示可以进行拷贝，在HashMap中，实现的是浅层次拷贝，即对拷贝对象的改变会影响被拷贝的对象；Serializable接口表示HashMap实现了序列化，即可以将HashMap对象保存至本地，之后可以恢复状态。
 

2：HashMap集合的实现：

      HashMap的实现使用了一个数组，每个数组里面有一个链表的方式来实现，因为HashMap使用key的hashCode来寻找存储位置，不同的key可能具有相同的hashCode，这时候就出现哈希冲突了，也叫做哈希碰撞，为了解决哈希冲突，有开放地址方法，以及链地址方法。HashMap的实现上选取了链地址方法，也就是将哈希值一样的entry保存在同一个数组项里面，可以把一个数组项当做一个桶，桶里面装的entry的key的hashCode是一样的。
　　在Java8之后，HashMap在原有的基础上实现了红黑树结构，当桶中链表长度超过8时，会转化为红黑树结构来存储，当链表长度小于6时，将红黑树转化为链表，使得在桶里面查找数据的复杂度从O(n)降到O(logn)
 　　HashMap的初始桶的数量为16，loadFact为0.75,当桶里面的数据记录超过阈值的时候，HashMap将会进行扩容则操作，每次都会变为原来大小的2倍，直到设定的最大值之后就无法再resize了。

3：HashMap的成员变量

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
-> 数组默认初始容量：16
static final int MAXIMUM_CAPACITY = 1 << 30;
-> 数组最大容量2 ^ 30 次方
static final float DEFAULT_LOAD_FACTOR = 0.75f;
-> 默认负载因子的大小：0.75
static final int MIN_TREEIFY_CAPACITY = 64;
-> 树形最小容量：哈希表的最小树形化容量,超过此值允许表中桶转化成红黑树
static final int TREEIFY_THRESHOLD = 8;
-> 树形阈值：当链表长度达到8时，将链表转化为红黑树
static final int UNTREEIFY_THRESHOLD = 6;
-> 树形阈值：当链表长度小于6时，将红黑树转化为链表
transient int modCount; -> hashmap修改次数
int threshold; -> 可存储key-value 键值对的临界值 需要扩充时;值 = 容量 * 加载因子
transient int size; 已存储key-value 键值对数量
final float loadFactor; -> 负载因子
transient Set< Map.Entry< K,V >> entrySet; -> 缓存的键值对集合
transient Node< K,V>[] table; -> 链表数组（用于存储hashmap的数据）

4：重写hashCode&&equals方法

如果没有重写 hashcode 方法，JDK 默认使用 Object 类 native 的 hashCode 方法，返回的是一般是一个与存储地址相关联的数

HashMap不能存储key值相同的数据，是因为在存储时，会先判断hashCode是否相同，紧接着equals继续判断

所以用到hashCode时，必然要重写hashCode和equals方法

例：写一个Student类，重写hashCode和equals方法

public class Student {

    private  String name;
    private int age;

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public String toString() {
        return this.name+"--"+this.age;
    }

    @Override
    public boolean equals(Object o) {
        Student student=(Student) o;
        return this.name.equals(student.name)&&this.age==student.age;
    }

    @Override
    public int hashCode() {
        return name.hashCode()+age*38;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }
}

5：resize机制

HashMap的扩容机制就是重新申请一个容量是当前的2倍的桶数组，然后将原先的记录逐个重新映射到新的桶里面，然后将原先的桶逐个置为null使得引用失效。

扩容处理会遍历所有的元素，时间复杂度很高；经过一次扩容处理后，元素会更加均匀的分布在各个桶中，会提升访问效率。所以我们尽量避免进行扩容处理，当我们知道需要存储数据的个数时，在newHashMap时就给定初始容量，避免重复扩容

给定扩容容量我们必须要给定容量大于我们预计数据量的 1.34 倍，并且为2的幂次方

例如：如果是2个数据的话，将初始化容量设置为4。

           如果预计大概会插入 12 条数据的话，那么初始容量为16简直是完美，一点不浪费，而且也不会扩容。

　　　 如果某个Map存储了10000个数据，那么他会扩容到 20000，实际上，根本不用 20000，只需要 10000* 1.34= 13400 个，然后向上找到一个2 的幂次方，也就是 16384 初始容量足够

6：为什么HashMap线程不安全

1>put的时候导致的多线程数据不一致。
这个问题比较好想象，比如有两个线程A和B，首先A希望插入一个key-value对到HashMap中，首先计算记录所要落到的桶的索引坐标，然后获取到该桶里面的链表头结点，此时线程A的时间片用完了，而此时线程B被调度得以执行，和线程A一样执行，只不过线程B成功将记录插到了桶里面，假设线程A插入的记录计算出来的桶索引和线程B要插入的记录计算出来的桶索引是一样的，那么当线程B成功插入之后，线程A再次被调度运行时，它依然持有过期的链表头但是它对此一无所知，以至于它认为它应该这样做，如此一来就覆盖了线程B插入的记录，这样线程B插入的记录就凭空消失了，造成了数据不一致的行为。

2>发生在扩容时，重新调整HashMap大小的时候，多个线程确实存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在LinkedList中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在LinkedList的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了，那么就死循环了。这个时候，你可以质问面试官，为什么这么奇怪，要在多线程的环境下使用HashMap呢？

　　

推荐阅读