首先得看java最基本的两种数据结构,数组和链表的区别:
而哈希表的出现是为了解决链表访问不快速的弱点,为了达到这一个目的:
哈希表中有一个哈希函数(散列函数)。即构建一个确定的映射,它能把关键字映射到一个唯一的存储位置。这种映射应该是我们可以进行计算的。已知关键字,我们应该能算出其地址;反之,已知地址,我们可以检索到对应的关键字。一旦建立起这种关系,那么给定关键字,我就能直接利用这个映射(即所谓的哈希函数)直接算出其地址并寻址。这可大大缩减确定关键字存储位置所花的时间。
HashSet是通过HashMap来实现的,HashMap的输入参数有Key、Value两个组成,在实现HashSet的时候,保持HashMap的Value为常量,相当于在HashMap中只对Key对象进行处理。
HashMap的底层是一个数组结构,数组中的每一项对应了一个链表,这种结构称“链表散列”的数据结构,即数组和链表的结合体;也叫散列表、哈希表。
想要了解HashMap和HashSet这样两个不同存储结构的区别,就得熟知他们的存储过程:
它的主要考点有:
冲突(Collision),是说两个不同的 key 经过哈希函数的计算后,得到了两个相同的值。解决冲突的方法,主要有两种:
哈希表容量的大小在一开始是不确定的。如果哈希表存储的元素太多(如超过容量的30%),我们应该将哈希表容量扩大一倍,并将所有的哈希值重新安排。
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实例化过程应该是怎样的? 与其在网上拼命找题? 不如马上关注我们~