数据结构：哈希表原理以及面试中的常见考点

阅读 1

2021-04-30

首先得看java最基本的两种数据结构，数组和链表的区别：

而哈希表的出现是为了解决链表访问不快速的弱点，为了达到这一个目的：

哈希表中有一个哈希函数(散列函数)。即构建一个确定的映射，它能把关键字映射到一个唯一的存储位置。这种映射应该是我们可以进行计算的。已知关键字，我们应该能算出其地址；反之，已知地址，我们可以检索到对应的关键字。一旦建立起这种关系，那么给定关键字，我就能直接利用这个映射(即所谓的哈希函数)直接算出其地址并寻址。这可大大缩减确定关键字存储位置所花的时间。

HashMap和HashSet的区别

HashSet是通过HashMap来实现的，HashMap的输入参数有Key、Value两个组成，在实现HashSet的时候，保持HashMap的Value为常量，相当于在HashMap中只对Key对象进行处理。

HashMap的底层是一个数组结构，数组中的每一项对应了一个链表，这种结构称“链表散列”的数据结构，即数组和链表的结合体；也叫散列表、哈希表。

想要了解HashMap和HashSet这样两个不同存储结构的区别，就得熟知他们的存储过程：

HashMap存储对象的过程

对HashMap的Key调用hashCode()方法，返回int值，即对应的hashCode；

把此hashCode作为哈希表的索引，查找哈希表的相应位置，若当前位置内容为NULL，则把HashMap的Key、Value包装成Entry数组，放入当前位置；

若当前位置内容不为空，则继续查找当前索引处存放的链表，利用equals方法，找到Key相同的Entry数组，则用当前Value去替换旧的Value；

若未找到与当前Key值相同的对象，则把当前位置的链表后移（Entry数组持有一个指向下一个元素的引用），把新的Entry数组放到链表表头；

HashSet存储对象的过程

往HashSet添加元素的时候，HashSet会先调用元素的hashCode方法得到元素的哈希值，

然后通过元素的哈希值经过移位等运算，就可以算出该元素在哈希表中的存储位置，存储时会出现两种情况：

情况1：如果算出元素存储的位置目前没有任何元素存储，那么该元素可以直接存储到该位置上。

情况2：如果算出该元素的存储位置目前已经存在有其他的元素了，那么会调用该元素的equals方法与该位置的元素再比较一次，如果equals返回的是true，那么该元素与这个位置上的元素就视为重复元素，不允许添加，如果equals方法返回的是false，那么该元素允许添加。

小结

HashSet和HashMap的区别

常见考点

它的主要考点有：

是否会灵活的使用哈希表解决问题

是否熟练掌握哈希表的基本原理

哈希冲突解决方法

小提示：

HashSet实现了Set接口，其内部不允许出现重复的值，如果我们将一个对象存入HashSet，必须重写equals()和hashCode()方法，这样才能确保集合中不存在同一个元素。HashSet的内部是无序的，因此不能使用 hashset.get(index) 来获取元素。

HashMap实现了Map接口，其内容是键值对的映射（key->value），不允许出现相同的键（key）。在查询的时候会根据给出的键来查询对应的值。

我们可以认为，HashSet和HashMap增查操作的时间复杂度都是常数级的。
推荐：
250期面试题汇总

哈希冲突解决方法

冲突（Collision），是说两个不同的 key 经过哈希函数的计算后，得到了两个相同的值。解决冲突的方法，主要有两种：

开散列法（Open Hashing）。是指哈希表所基于的数组中，每个位置是一个 Linked List 的头结点。这样冲突的 <key,value> 二元组，就都放在同一个链表中。

闭散列法（Closed Hashing）是指在发生冲突的时候，后来的元素，往下一个位置去找空位。

哈希表的扩容

哈希表容量的大小在一开始是不确定的。如果哈希表存储的元素太多（如超过容量的30%），我们应该将哈希表容量扩大一倍，并将所有的哈希值重新安排。

扩展：HashFunction的实现

public class Solution {
    /**
     * @param key: A string you should hash
     * @param HASH_SIZE: An integer
     * @return: An integer
     */
    public int hashCode(char[] key, int HASH_SIZE) {
        // write your code here
        long ans = 0;
        for(int i = 0; i < key.length; i  ){
            ans = (ans * 33   (int)(key[i])) % HASH_SIZE;
        }
        return (int)(ans);
    }
}

来源：blog.csdn.net/m0_55221239/article/details/1145324039

 
  END
 


 十期推荐
 
  【261期】面试官：说出几个你熟悉的 Zookeeper 命令
  

 
 
  【262期】面试官：谈谈MySQL主从复制的原理
  

 
 
  【263期】面试最后一问：你有什么要问我的吗？
  

 
 
  【264期】盘点MySQL主从复制，在面试中能被问什么？
  

 
 
  【265期】面试官：为什么Integer用==比较时127相等而128不相等？
  

 
 
  【266期】面试官：Redis主从集群切换数据丢失问题如何应对？
  

 
 
  【267期】10道经典MySQL面试题
  

 
 
  【268期】美团面试题：当你的JVM 堆内存溢出后，其他线程是否可继续工作？
  

 
 
  【269期】链表高频面试题（包括反转、合并、相交、分割、环长等）
  

 
 
  【270期】面试官：Spring的Bean实例化过程应该是怎样的？
  

 
 
  

 
？ ~

以上数据来源于网络，如有侵权，请联系删除。

上一篇：面试官：Spring MVC的处理流程是怎样的？

下一篇：告诉面试官，我能优化groupBy，而且知道得很深！

类别