哈希表的详细和其实现~
哈希冲突:不同的关键字通过相同的哈希函数,有可能找到相同的位置
如何避免冲突:(冲突的发生是必然的,但我们能做的应该是尽量的降低冲突率)
1、设计哈希函数来比避免冲突
(1)哈希函数的定义域必须包括需要存储的全部关键码,而如果散列表允许有m个地址时,其值域必须在0到m-1 之间,就是散列表有多少格子就用多少格子的意思
(2)哈希函数计算出来的地址能均匀分布在整个空间中
常见哈希函数:
1. 直接定制法 --(常用 )取关键字的某个线性函数为散列地址: Hash ( Key ) = A*Key B 优点:简单、均匀缺点:需要 事先知道关键字的分布情况 使用场景: 适合查找比较小且连续的情况面试题:字符串中第一个只出现一次字符
思路:因为知道了字符串中都是小写字母,就是 事先知道关键字的分布情况小写字母还是连续的并且范围较小,所以可以用哈希的方法
public int firstUnique(String s){ if(s==null){ return -1; } int[] array=new int[26]; for (int i = 0; i < s.length(); i ) {//第一次遍历str,把里面的元素都放入array里 char ch=s.charAt(i); array[ch-97] ; } for (int i = 0; i <s.length() ; i ) {//第二次遍历str,每遍历一个元素上array里检查一下,若为1,则返回 char ch=s.charAt(i); if(array[ch-97]==1){ return i; } } return -1; }2. 除留余数法--(常用)
设散列表中允许的 地址数为 m ,取一个不大于 m ,但最接近或者等于 m 的质数 p 作为除数,按照哈希函数: Hash(key) = key% p(p<=m), 将关键码转换成哈希地址
负载因子=存储散列表元素的个数/散列表的长度(负载因子=0.75,一旦大于0.75需要调节)
负载因子和冲突的关系:
可知:负载因子越小,冲突率越低
要想降低冲突,需要将负载因子降低,由于存储散列表元素的个数在慢慢增加,所以要想负载因子降低只能提高散列表的长度,因此要想降低冲突,需要提高散列表的长度
由于冲突是避免不了的,那真正发生冲突又该怎么解决呢?
1、闭散列(开放地址法):就是去寻找下一个为空的位置
(1)线性探测:从冲突的位置开始向后找找到第一个为空的位置将元素放进去
缺点:会把冲突的元素都放到一起了,这样就不能随便删除哈希表中已有的元素,若直接删除元素会影响其他元素的搜索。比如删除元素4,如果直接删除掉,44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。
(2)二次探测:
缺点:空间利用率较低,只能装一半的元素,如果超出必须考虑增容。
2、(重点)开散列(哈希桶HashBuck/链地址法/开链法)
底层就是:数组(数组里面存的是Node) 链表
有人会担心,链表长度万一很长,遍历的时候时间复杂度不就会变成O(N)嘛?
这点请放心,因为链表的长度不会很长,控制在常数范围内,因为需要控制负载因子。
从JDK1.8开始,当链表长度超过8,并且数组的长度超过64时,这个链表就会变成红黑树
红黑树查找非常高效,不用担心时间复杂度问题。
通常认为哈希表的插入/删除/查找时间复杂度是 O(1)
1、简单实现哈希表~
-
public class HashBuck {
-
static class Node{
-
public int key;
-
public int val;
-
public Node next;
-
public Node(int key,int val){
-
this.key=key;
-
this.val=val;
-
}
-
}
-
public Node[] array;
-
public int usedSize;
-
-
public static final double DEFAULT_LOAD_FACTOR=0.75;//规定负载因子,添加数据时检查一下,防止冲突
-
-
public HashBuck(){
-
this.array=new Node[10];
-
}
-
//添加元素
-
public void put(int key,int val){
-
//1、找到key所对应在array中的位置
-
int index=key% array.length;
-
//2、遍历index位置的链表,看key是否重复,重复则替换,若key不在则插入链表中
-
//2.1重复的时候
-
Node cur=array[index];
-
while(cur!=null){
-
if(cur.key==key){
-
cur.val=val;//key重复,替换val
-
return;
-
}
-
cur=cur.next;
-
}
-
//2.2不重复的时候:头插法插入
-
Node node=new Node(key, val);
-
node.next=array[index];//绑定尾部
-
array[index]=node;//绑定头部
-
usedSize ;
-
//3、检查负载因子,超出负载因子的值,则需要扩大array的容量来减小负载因子的值,防止冲突
-
if(loadFactor()>=DEFAULT_LOAD_FACTOR){
-
resize();//扩容array的方法
-
}
-
}
-
//扩容array需要注意:此时由于array扩容变长 需要将原来没扩容之前的节点都拿出来,
-
// 然后重新哈希每个节点找在扩容后数组中的位置
-
private void resize(){
-
Node[]newArray=new Node[2*array.length];
-
for (int i = 0; i < array.length; i ) {//遍历原来的数组,将里面的节点全都拿出来
-
Node cur=array[i];//拿里面的节点
-
while(cur!=null){//有可能array里的每个位置里都不止一个节点,而是一个链表
-
int index=cur.key%newArray.length;//找到节点在扩容后数组中的位置
-
Node curNext=cur.next;
-
cur.next=newArray[index];//绑定后面
-
newArray[index]=cur;//绑定前面
-
cur=curNext;
-
}
-
}
-
array=newArray;//让扩容后的数组代替原来的数组
-
}
-
-
private double loadFactor(){//求当前的负载因子值
-
return 1.0*usedSize/array.length;//负载因子=当前数据长度/数组长度
-
}
-
-
//根据key获取val值
-
public int get(int key){
-
//1、找key的位置(大概找到key所在array数组的哪个下标里)
-
int index=key%array.length;
-
//2、遍历这个下标的链表具体找到key
-
Node cur=array[index];
-
while(cur!=null){
-
if(cur.key==key){
-
return cur.val;
-
}
-
cur=cur.next;
-
}
-
return -1;
-
}
-
-
public static void main(String[] args) {
-
HashBuck hashBuck=new HashBuck();
-
hashBuck.put(1,1);
-
hashBuck.put(2,2);
-
hashBuck.put(4,4);
-
hashBuck.put(6,6);
-
hashBuck.put(13,13);
-
hashBuck.put(12,12);
-
hashBuck.put(11,11);
-
hashBuck.put(8,8);
-
System.out.println(hashBuck.get(11));
-
}
-
}
关于hashCode函数:可以使一个引用变成一个合法的整数
//假设接下来的key是一个person,身份证号是一样的,我们认为是同一个人 //又因为,要把person1和person2放到散列表中,需要找到index,所以需要调用person.hashcode(),找到下标 class Person{ public String ID; public Person(String ID){ this.ID=ID; } public String toString() { return "Person{" "ID='" ID '\'' '}'; } } public static void main(String[] args) { Person person1=new Person("123"); Person person2=new Person("123"); System.out.println(person1.hashCode()); System.out.println(person2.hashCode()); }因为是同一个人,所以需要生成的值是一样的,这样才能存到同一位置,可是按照上面显然是不能达到预期的,因此还需要加东西,让生成的hashCode值相同
class Person{ public String ID; public Person(String ID){ this.ID=ID; } public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Person person = (Person) o; return Objects.equals(ID, person.ID); } public int hashCode() { return Objects.hash(ID); } public String toString() { return "Person{" "ID='" ID '\'' '}'; } } public class HashBuck2 { public static void main(String[] args) { Person person1=new Person("123"); Person person2=new Person("123"); System.out.println(person1.hashCode()); System.out.println(person2.hashCode()); } }重写了hashCode和equals后发现生成的值相等了,满足了预期
总结:因为HashMap底层是一个哈希表,所以在使用HashMap时如果map里面存的key值是自定义类型,一定要重写HashCode
像这种情况就要重写。 否则就会出现本意是一个人的两个人,最终被误认为不是一个人,被放到了不同位置
2、改进实现哈希表
-
import java.util.Objects;
-
//改进哈希表(由于哈希表里面的值不一定是整数)
-
class Person{
-
public String ID;
-
public Person(String ID){
-
this.ID=ID;
-
}
-
-
-
public String toString() {
-
return "Person{"
-
"ID='" ID '\''
-
'}';
-
}
-
//如果哈希表里存的树自定义对象时,在进行插入和查找时要重写equals()和hashCode()两个方法
-
-
public boolean equals(Object o) {
-
if (this == o) return true;
-
if (o == null || getClass() != o.getClass()) return false;
-
Person person = (Person) o;
-
return Objects.equals(ID, person.ID);
-
}
-
-
-
public int hashCode() {
-
return Objects.hash(ID);
-
}
-
}
-
public class HashBuck2 <K,V>{
-
static class Node<K,V>{
-
public K key;
-
public V val;
-
public Node<K,V> next;
-
public Node(K key,V val){
-
this.key=key;
-
this.val=val;
-
}
-
}
-
-
public Node<K,V>[] array=(Node<K,V>[])new Node[10];
-
public int usedSize;
-
public void put(K key,V val){
-
int hash=key.hashCode();//通过hashCode()来将一个字符串转换成对应值,
-
// 进而通过生成的值来找其在array数组中的位置
-
int index=hash%array.length;
-
Node<K,V> cur=array[index];
-
while(cur!=null){
-
if(cur.key.equals(key)){
-
cur.val=val;
-
return;//此时相同的值再次插入,替换完val值后return
-
}
-
cur=cur.next;
-
}
-
Node<K,V> node=new Node<>(key,val);
-
node.next=array[index];
-
array[index]=node;
-
this.usedSize ;
-
}
-
public V get(K key){
-
int hash=key.hashCode();
-
int index=hash%array.length;
-
Node<K,V> cur=array[index];
-
while(cur!=null){
-
if(cur.key.equals(key)){
-
return cur.val;
-
}
-
cur=cur.next;
-
}
-
return null;
-
}
-
-
public static void main(String[] args) {
-
Person person1=new Person("123");
-
Person person2=new Person("123");
-
HashBuck2<Person,String> hashBuck2=new HashBuck2<>();
-
hashBuck2.put(person1,"ly");
-
System.out.println(hashBuck2.get(person2));
-
}
-
-
public static void main1(String[] args) {
-
Person person1=new Person("123");
-
Person person2=new Person("123");
-
System.out.println(person1.hashCode());
-
System.out.println(person2.hashCode());
-
}
-
-
-
}
总结:1. HashMap 和 HashSet 即 java 中利用哈希表实现的 Map 和 Set2. java 中使用的是哈希桶方式解决冲突的3. java 会在冲突链表长度大于一定阈值后,将链表转变为搜索树(红黑树)4. java 中 计算哈希值 实际上是 调用的类的 hashCode 方法 , 进行 key 的相等性比较 是调用 key 的 equals方 法 。所以 如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值,必须覆写 hashCode 和 equals 方法 ,而且要做到 equals 相等的对象, hashCode 一定是一致的
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgaghae
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
photoshop蒙版画笔没反应怎么办
PHP中文网 06-24