[Java]源码角度深入理解哈希表,手撕常见面试题

 

专栏简介 :java语法及数据结构

题目来源:leetcode,牛客,剑指offer

创作目标:从java语法角度实现底层相关数据结构,达到手撕各类题目的水平.

希望在提升自己的同时,帮助他人,,与大家一起共同进步,互相成长.

学历代表过去,能力代表现在,学习能力代表未来!

---

目录 

前言

一.哈希表的概念:

二.哈希冲突:

三.避免哈希冲突:

1.合理设置哈希函数:

2.负载因子调节:

四.解决哈希冲突:

1.闭散列:

2.开散列-哈希桶:

五.HashMap与TreeMap的区别:

六.哈希表的实现:

七.哈希函数的应用

1.10万个数据去重.

2.10万个数据中第一个重复的数据.

3.统计十万个数据中每个数据出现的的次数.

八.面试常见问题:

1.创建哈希表时如果不初始化大小那么哈希表的大小的多少?

2.创建哈希表时如果初始化大小那么一定和初始化的一样吗?

3.hashcode与equals的联系与区别?

4.HashMap如果满了,如何重新hash?

5.哈希表是如何树化的?

6.哈希表树化后为什么可以比较了?

九.性能分析:

总结

---

前言

        最近收到许多佬们的私信,吐槽我一篇文章内容写的太多建议更加细化每一个板块,于是我决定将哈希表从Map与Set中剥离,深入且详细的写一篇文章,希望能够让大家有所收货!!

---

一.哈希表的概念:

• 在顺序结构或平衡树中,元素与关键码没有对应关系,因此搜索元素必须经过关键码的多次比较,最慢O(N),最快O(logN).搜索快慢取决于查找元素时的比较次数.
• 那么如果让元素的关键码与存储位置通过某种函数建立映射关系,那么在查找时就可以通过该函数很快的找到该元素.

该方法称为哈希(散列)法:哈希法中使用的转换函数叫做哈希函数,构造出的结构叫做哈希表.

eg:集合{1 , 7 , 6 , 4 , 5 , 9}.

哈希函数设置为:hash = key%capacity. (capacity = 10);

 使用该方法可以根据映射关系直接找出不必多次比较所以较快,但如果我们插入11,就会发现与1位置重复了.这就是哈希冲突.

---

二.哈希冲突:

• 不同关键字通过相同哈希函数计算出相同哈希地址,这样的情况叫做哈希冲突.

---

三.避免哈希冲突:

• 首先我们要明确由于哈希表底层是数组,那么其实际容量往往小于要存储关键字的数量,既然哈希冲突无法避免,我们要做的就是尽可能的降低哈希冲突.

1.合理设置哈希函数:

1.1哈希函数设计原则:

• 哈希函数定义域必须包含所有关键码.
• 哈希函数计算出的地址能均匀的分布在整个空间.
• 哈希函数应该比较简答.

1.2常见哈希函数:

• 1.直接定制法:

  取关键字的某个线性函数为哈希地址,Hash = A*Key +B.虽然简单,但需要事先知道关键字的分布情况.例如:在一个大小为10的哈希表中存放82,Hash = 1*82-80.所以将其存放在下标为2的位置.

• 应用:(字符串中第一个只出现一次的字符)

因为只存放小写字母所以创建一个大小为26的整形数组,遍历字符串,字符下标减去'a',就是直接定制法思想的体现.

class Solution {
    public char firstUniqChar(String s) {
        int[] arr = new int[26];
        for(int i = 0;i
            char ch = s.charAt(i);
            arr[ch-'a']++;
        }
        for(int i = 0;i
            char ch = s.charAt(i);
            if(arr[ch-'a']==1){
                return ch;
            }
        }
        return ' ';
    }
}

• 2.除留取余法:

设哈希表表的大小为m,取一个不大于m,但最接近m或等于m的质数p作为除数.Hash = key%p,将关键码转化为哈希地址.

Tips:哈希函数设置的越精妙,哈希冲突产生的概率就越低,但无法避免哈希冲突.

---

2.负载因子调节:

• 哈希表的载荷因子 α  = 填入表中元素个数/哈希表的长度.
• α是哈希表装满程度的标志因子,与哈希表表中填入元素的个数成正比.

负载因子和冲突率的粗略演示:

• 由上图可知:负载因子的大小应严格的控制在0.7-0.8以下,超过0.8查表时冲突率按照指数上升,因此Java库中严格的限制载荷因子为0.75,超过这个大小就会调用resize()方法扩大哈希表.
• 因此避免哈希冲突可以采用降低负载因子的做法,由于关键字的个数无法改变, 所以只能扩大哈希表的大小.

---

四.解决哈希冲突:

1.闭散列:

闭散列也叫开放定址法,当发生哈希冲突时,如果哈希表还未填满,可以把冲突元素Key存放到冲突位置的下一个空位置去.关键在于如何寻找到下一个空位?

• 线性探测:从发生冲突的位置开始依次向后,找到空位插入.

这种方法虽然简便但带来的弊端是,发生哈希冲突的key可能堆在一起,这与哈希表的设计初衷相悖.并且由于哈希表中的某个key可能记录好多冲突key的位置,如果贸然删除会丢失很多key的位置,因此线性探测采用标记的伪删除法来删除某个元素.

• 二次探测:

二次探测可以有效的避免线性探测将冲突的Key堆积在一起,其计算下一个位置的方法是:

Hi = (Ho+i^2)%m或者Hi = (Ho-i^2)%m.其中Ho是通过哈希函数计算得到的位置,Hi是二测探测重新分配的位置,i的冲突的次数.

---

2.开散列-哈希桶:

开散列法又叫链地址法,首先对关键码集合用哈希函数计算哈希地址,具有相同地址的关键码归于同一个子集合,每一个子集合称做一个同,桶中每一个关键字用单链表连接起来,个链表的头结点储存在哈希表中.

• 由图可以看出,每个桶中放的都是发生哈希冲突的元素.
• 开散列法,相当于将大集合中搜索转化为小集合中.
• 当发生严重冲突时导致链表长度过长,JAVA底层会在链表长度大于8并且哈希表长度大于64时,自动转化为红黑树.(若哈希表长度不足64,依旧是链表的形式)

---

五.HashMap与TreeMap的区别:

1.本质区别:

• 从类的定义来看:HashMap和TreeMap继承自AbstractMap,不同的是HashMap实现的是Map接口,TreeMap实现的是NavigableMap接口,NavigableMap接口是SortedMap的一种,实现了Map中key的排序.所以TreeMap中key是排序且可比较的,HashMap不是.
• HashMap的定义:

public class HashMap extends AbstractMap
    implements Map, Cloneable, Serializable

• TreeMap的定义:

public class TreeMap
    extends AbstractMap
    implements NavigableMap, Cloneable, java.io.Serializable

• 再看构造函数的区别:

public HashMap(int initialCapacity, float loadFactor) 

HashMap除了默认的无参构造函数之外,还可接收两个参数 initialCapacity 和 loadFactor

transient Node[] table

HashMap的底层是Node数组.

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

initialCapacity就是这个数组的初始容量,如果不传长度,HashMap默认为2^4=16.

static final float DEFAULT_LOAD_FACTOR = 0.75f;

当哈希表负载因子达到一定大小,为了避免哈希冲突,HashMap就会2倍扩容.而loadFactor指定了什么时候扩容的操作,默认loadFactor的大小是0.75.

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;

JDK8以前HashMap解决哈希冲突的方法是纯链地址法,为了提升查找效率,JDK8将其改为链表转化为红黑树,什么时候转换呢?这就与以上三个变量有关了.TREEIFY_THRESHOLD=8代表链表的长度大于8就会转换,MIN_TREEIFY_CAPACITY=64代表哈希表的长度大于64就会转换.UNTREEIFY_THRESHOLD=6代表当链表的长度小于6就由红黑树退化为单链表.

private transient Entry root

TreeMap的底层是一个Entry,它由红黑树来实现.

public TreeMap(Comparatorsuper K> comparator) {
        this.comparator = comparator;
    }

TreeMap的构造方法还可传入一个自定义比较器.如果不传入使用cpp编写的Native order.

---

2.性能区别:

• HashMap的底层是数组所以在增删改查时会非常快,TreeMap底层是树速度较慢.
• 数组比起链表构成的树空间利用率会更低.
• TreeMap在插入时会排序,所以效率收到影响.

---

六.哈希表的实现:

public class HashBuck {
    static class Node{
        public K key;
        public V value;
        public Node next;
 
        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
    Node[] array = (Node[]) new Node[8];
    public int usedSize;
 
    public void put(K key,V value){
        int hash = key.hashCode();//获取对象哈希值
        int index = hash%array.length;
        Node cur = array[index];
        //覆盖重复的key
        while (cur !=null){
            if (cur.key.equals(key)){
                cur.value=value;
                return;
            }
            cur = cur.next;
        }
        //若没有重复key使用头插法插入节点.
        Node node = new Node<>(key,value);
        node.next = array[index];
        array[index] = node;
        usedSize++;
        if (loadFactor()>=0.75f){
            resize();//扩容
        }
    }
    private float loadFactor(){//计算负载因子
        return usedSize*1.0f/array.length;
    }
    private void resize(){
        Node[] newArray = new Node[array.length*2];//二倍扩容
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            while (cur!=null){
                Node curNext = cur.next;
                int hash = cur.key.hashCode();
                int newIndex = hash%array.length;
                //拿着cur节点插入到新位置
                cur.next = newArray[newIndex];
                newArray[newIndex] = cur;
                cur = curNext;
            }
        }
        //newArray仅仅是一个局部变量,将其赋给array
        array = newArray;
    }
    public V get(K key){
        int hash = key.hashCode();
        int index = hash%array.length;
        Node cur = array[index];
        while (cur!=null){
            if (cur.key==key){
                return cur.value;
            }
            cur = cur.next;
        }
        throw new RuntimeException("没有该键值对");
    }
    
}

---

七.哈希函数的应用

• 10万个数据去重.

public static void func1(int[] array){
        HashSet set = new HashSet<>();
        for (int i = 0; i < array.length; i++) {
            set.add(array[i]);
        }
        System.out.println(set);
    }
    public static void main(String[] args) {
        int[] array = new int[10_0000];
        Random random = new Random();
        for (int i = 0; i < array.length; i++) {
            array[i] =  random.nextInt(5_0000);
        }
        func1(array);
    }

• 10万个数据中第一个重复的数据.

public static void func2(int[] array){
        HashSet set = new HashSet<>();
        for (int i = 0; i < array.length; i++) {
            if (set.contains(array[i])){
                System.out.println(array[i]);
                return;
            }else {
                set.add(array[i]);
            }
        }
        System.out.println(set);
    }
    public static void main(String[] args) {
        int[] array = new int[10_0000];
        Random random = new Random();
        for (int i = 0; i < array.length; i++) {
            array[i] =  random.nextInt(5_0000);
        }
        func2(array);
    }

• 统计十万个数据中每个数据出现的的次数.

public static void func3(int[] array){
        HashMap hashMap = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            if (hashMap.get(array[i])==null){
                hashMap.put(array[i],1 );
            }else {
                int val = hashMap.get(array[i]);
                hashMap.put(array[i],val+1);
            }
        }
        System.out.println(hashMap);
    }
    public static void main(String[] args) {
        int[] array = new int[10_0000];
        Random random = new Random();
        for (int i = 0; i < array.length; i++) {
            array[i] =  random.nextInt(5_0000);
        }
        func3(array);
    }

---

八.面试常见问题:

1.创建哈希表时如果不初始化大小那么哈希表的大小的多少?

首先查看HashMap的无参构造函数,其中并无初始化哈希表的相关操作.因此推断出只有在HashMap调用put方法时才会初始化大小.

 

其次查看put方法时发现其返回值调用了putVal方法,在putVal方法中发现当哈希表为空或者哈希表大小为0时,为数组长度赋值会调用resize()方法 .

 

由于resize()方法内容过多,所以只看本题需要的部分.在此方法中会判断原数组的大小,如果原数组大小为0,就会给newCap赋值为默认初始化大小1>>>4 也就是(16).然后再以newCap为大小创建一个新数组,最后返回这个新数组.

---

2.创建哈希表时如果初始化大小那么一定和初始化的一样吗?

观察HashMap带一个参数的构造方法,发现其使用this()方法调用了HashMap两个参数的构造方法. 

在HashMap的两个参数的构造方法中发现,最初传入的参数19,并不符合前三个if语句.所以继续查看tableSizeFor(initialCapacity)方法.

 该方法中有一句英文提示:返回给定容量大小的2次幂 ,由此可以推断出数组的大小只可能是16或者32,由于返回16一定放不下19个元素所以遵守向上取整的原则返回32.

---

3.hashcode与equals的联系与区别?

自学习Java后总是听到新建类想要具有可比较性必须重写hashcode和equals方法,对于这种说法总是云里雾里.随着学习的不断深入,在哈希表中感悟到了更加形象的描述方法.

类比于查询字典,假如我们要查询美女那么首先要查到美这类词,然后在这类词中查询美女这个单词.因此hashcode就相当与查询到了数组中美这个下标,但美之后还用链表连接着很多词语例如:美丽.美食.美景....想要查询到美女还要调用equals方法.

这时就会有疑问感觉直接调用equals方法就可以完成比较,为什么还要重写hashcode()方法? 

•  java API文档中解释:如果两个对象通过调用equals方法是相等的那么这两个对象调hashCode方法必须返回相同的整数。
• 通俗解释,集合类中Set集合中元素是可比较且不重复的,每插入一个元素就使用equals比较一次,那么如果集合中有1000个元素再次插入需比较1001次这显然非常低效.所以hashcode可以缩小查找范围,非常有效的提升效率.

---

4.HashMap扩容机制?

1.什么时候才需要扩容?

• HashMap使用无参构造方法,首次调用put()方法时.
• HashMap中元素个数除以数组长度大于负载因子时就会扩容.
• HashMap中其中一个链表对象的值如果达到8个但此时数组长度未达到64,HashMap会先扩容解决.如果达到64就会变成红黑树,节点类型由Node变为TreeNode.

2.HashMap如何扩容?

进行扩容时会创建新数组,那么之前的hash值需要重新分配.

 这里比较重要就是(h = key.hashCode())^(h>>>16);意思是将生成的哈希值前16位和16位进行异或操作,那么为什么要这么做?

hash函数的作用是确定key在哈希表中的下标,如果每次扩容都遍历哈希表中的每一个元素重新计算哈希值会十分耗费时间,为了追求高性能JDK中通常这样写:

index = (table.length-1)&key.hash();

 这就解释了为什么哈希表扩容总是2的整数倍,这样有利于构造位运算快速寻址.新扩容的哈希表中元素的位置要么不变要么就变成原位置加扩容大小.

回到最初的话题,既然计算出的哈希值要与table.length-1做与运算,那么参与运算的只有hash值的最低位,为了让哈希表中元素分配的更加散列降低哈希冲突,那么哈希值的低位中含有高位信息(也就是让高位和地位都参与运算)就可以达到这一目的.

---

5.哈希表是如何树化的?

putVal()中有一个方法值得注意,当元素个数binCount>=8时会调用treeifyBin()方法.

 treeifyBin()方法中还要判断哈希表的长度是否大于MIN_TREEIFY_CAPACITY(64),如果不大于继续resize()扩容操作,如果大于就将Node类型转化为TreeNode类型变成一颗红黑树.

---

6.哈希表树化后为什么可以比较了?

在putVal方法中,如果判断哈希表中元素为TreeNode类型,就调用putTreeVal()方法.

在该方法中先判断是否有compable接口或者comparator比较器,如果没有就调用tieBreakOrder()方法.

在该方法中直接比较系统生成的hashCode().

---

九.性能分析:

• 虽然哈希表长期与冲突作斗争,但通常认为冲突个数是可控的,也就是每个桶中链表的长度是常数,所以通常情况下哈希表的插入\查找\删除元素的实现复杂度为O(1).

---

总结

        由于本人才疏学浅哈希表树化底层实现原理的讲述还要推迟,预计会和红黑树专题一块写.如有不足之处还请各位斧正!!