HashMap相关知识点

2020-05-12 | 阅读：次 |本站总访问量次 | 本站访客数人

什么是哈希表？什么是哈希冲突？HashMap的原理？

哈希表是基于数组的一种存储方式，它主要由哈希函数和数组组成。

当要存储一个数据的时候，首先用一个函数计算数据的地址，然后再将数据存进指定地址位置的数组里面。这个函数就是哈希函数，而这个数组就是哈希表。

哈希表的优势

相比于简单的数组以及链表，它能够根据元素本身在第一时间，也就是时间复杂度为0（1）内找到该元素的位置。这使得它在查询和删除、插入上会比数组和链表要快很多。因为他们的时间复杂度为o(n)。

哈希冲突

哈希冲突是指哈希函数算出来的地址被别的元素占用了。好的哈希函数会尽量避免哈希冲突。

解决哈希冲突的办法

开放定址法，发生冲突，继续寻找下一块未被占用的存储地址。

再散列法，就是再使用哈希函数去散列一个输入的时候，输出是同一个位置就再次散列，直至不发生冲突位置。

拉链法，HashMap，HashSet其实都是采用的拉链法来解决哈希冲突的，就是在每个位桶实现的时候，我们采用链表（jdk1.8之后采用链表+红黑树）的数据结构来去存取发生哈希冲突的输入域的关键字（也就是被哈希函数映射到同一个位桶上的关键字）。

HashMap与拉链法（链地址法）

当没有发生哈希冲突的时候Hashmap主要只有数组。但是当发生冲突的时候，它会在哈希函数找到的当前数组内存地址位置下添加一条链表。

HashMap和HashTable的区别

1.线程是否安全：HashMap是非线程安全的，HashTable是线程安全的。HashTable内部的方法基本都经过synchronized修饰。（如果你要保证线程安全的话就使用CocurrentHashMap）

2.效率：因为线程安全的问题，HashMap要比HashTable效率高一些，另外HashTable基本被淘汰，当不要求线程安全的情况下，使用HashMap，要求的话，使用CocurrentHashMap。

3.对Null Key和Null Value的支持：HashMap中，null可以作为键，这样的键只能有一个，可以有一个或多个键所对应的值为null。但是，在HashTable中put进的键值只要有一个null,直接抛出NullPointerException。

4.初始容量大小和每次扩充容量大小的不同：

<1>.创建时如果不指定容量初始值，HashTable默认的初始大小为11，之后每次扩充，容量变为原来的2n+1.HashTable默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。

<2>.创建时，如果给定了容量初始值，那么HashTable会直接使用你给定的大小，而HashMap会将其扩充为2的幂次方大小（HashMap中tableSizeFor（）方法保证）也就是HashMap总是使用2的幂次作为哈希表的大小，下篇文章会介绍到为什么是2的幂次方。

5.底层数据结构：JDK1.8以后的HashMap在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转换为红黑树，以减少搜索时间。HashTable没有这样的机制。

HashMap中带有初始容量的构造函数：

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) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
 }     

下面这个方法保证了HashMap总是使用2的幂作为哈希表的大小。

/**
     * Returns a power of two size for the given target capacity.
     */
    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;
    }

HashMap和HashSet区别

HashSet底层就是基于HashMap实现的。HashSet的源码非常少，因为除了clone(),wirteObject(),readObject()是HashSet自己不得不实现之外，其他方法都是直接调用HashMap中的方法。

HashSet如何检查重复

当你把对象加入HashSet时，HashSet会先计算对象的HashCode值来判断对象加入的位置，同时也会与其他加入的对象的HashCode值作比较，如果没有相符的HashCode，HashSet会假设对象没有重复出现。但是如果发现有相同HashCode值的对象，这时会调用equals（）方法来检查HashCode相等的对象是否真的相同。如果两者相同，HashSet就不会让加入操作成功。

hashcode（）与equals（）的相关规定：

1.如果两个对象相等，则hashcode一定也是相同的

2.两个对象相等，equals方法返回true

3.两个对象有相同的hashcode值，它们也不一定是相等的

4.综上，equals方法被覆盖过，则hashcode方法也必须被覆盖

5.hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode(),则该class的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）。

==与equals的区别

1）对于==，如果作用于基本数据类型的变量，则直接比较其存储的 “值”是否相等；如果作用于引用类型的变量，则比较的是所指向的对象的地址 2）对于equals方法，注意：equals方法不能作用于基本数据类型的变量如果没有对equals方法进行重写，则比较的是引用类型的变量所指向的对象的地址；诸如String、Date等类对equals方法进行了重写的话，比较的是所指向的对象的内容。

肖申克赫本