devbox
神奇cpp
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Java数据结构——哈希表_java中哈希表

作者：神奇cpp | 2024-07-01 08:16:22

赞

踩

java中哈希表

一.概念

哈希散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表

二. HashMap类

1. 概述

HashMap是基于哈希表的Map接口实现，属于双列集合的一种，其存储数据的特点是无序，不重复，无索引

2. 特有方法

HashMap的方法与Map基本一致\n\ngetOrDefault( key,默认值)\n\n判断哈希表中是否存在key,若存在则返回key的value值，不存在则返回默认值\n\n这个方法可厉害了，在力扣的部分解题中很有帮助\n\n如:如何让哈希表中的一个键key对应多个值\n\n首先我们肯定会想到值用链表结构类型，在每次找键插值时，我们要先获取key的链表，再将value插入链表中，最后再用put覆盖将链表再次插入到key中

 

三. HashMap代码实现

⑴底层基本原理

7a51fd01990c4c29b4115cd92f745318.png

在JDK8以前，哈希表的底层结构是数组+链表，JDK8以后，为了优化性能，又加入了红黑树，当数组长度超过64且链表长度大于等于8，链表会优化为红黑树

下面我们主要来了解最初的底层结构原理

1.首先数组中存储的是键值对对象Entry

2.在创建哈希表时，会默认创建一个长度为16，加载因子为0.75的数组table

3.添加元素时，底层会根据键的哈希值与数组长度的关系计算出应插入的数组位置，若哈希值冲突，会将新元素以链表的形式添加到冲突位置的后面

⑵代码实现

知道了哈希表的基本底层原理，下面我们就来实现HashMap中最基本的操作

1.键值对对象Entry

首先键值对对象一定要有键key和值value以及用来计算存入位置的哈希码hash

又因为当哈希冲突时我们要将新元素以链表的形式添加，所以我们还需要一个用来记录键值对插入位置的指针next

  1. static class Entry<K, V> {
  2.         /**
  3.          * 键值对
  4.          */
  5.         final int hash;//键的哈希值
  6.         final K key;//键唯一
  7.         V value;//值
  8.         Entry<K, V> next;//哈希值冲突的键值对用链表连接
  9.         public Entry(int hash, K key, V value) {
  10.             this.hash = hash;
  11.             this.key = key;
  12.             this.value = value;
  13.         }
  14.         @Override
  15.         public boolean equals(Object o) {
  16.             if (this == o) return true;//地址值相同
  17.             if (o == null || getClass() != o.getClass()) return false;//地址值不同
  18.             Entry<?, ?> entry = (Entry<?, ?>) o;
  19.             return Objects.equals(key, entry.key);
  20.         }
  21.         @Override
  22.         public final int hashCode() {
  23.             return Objects.hashCode(key) ^ Objects.hashCode(value);
  24.         }
  25.         @Override
  26.         public String toString() {
  27.             return key+"="+value;
  28.         }
  29.     }

2.MyHashMap

我们主要实现哈希表的添加put，删除remove，查找get等操作

⑴初始成员变量

首先当我们创建哈希表的对象时，底层会自动创建一个默认长度为16且加载因子为0.75的数组table,当数组中已经存在的元素个数size大于数组的可存入最大数组长度（数组长度*加载因子）时，数组就要进行扩容

  1.     Entry[] table = new Entry[16];//初始数组长度
  2.     int size = 0;//已存数组长度
  3.     final double DEFAULT_LOAD_FACTOR = 0.75d;//加载因子
  4.     int threshold = (int) (table.length * DEFAULT_LOAD_FACTOR);//可存入的最大数组长度
  5.     public MyHashMap() {}

⑵添加put

e73849a0ae8842d6a6f0adde3e0c5a9b.png

我们根据哈希码与数组长度的关系（hash&(数组长度-1)）来确定键值对的位置

若确定的数组位置中没有元素null，则将元素直接插入

若确定的数组位置中有元素，则遍历此位置的链表，若键存在，则将原来的值覆盖并返回，若键不存在，则插入链表尾部

  1. public void put(K key, V value) {
  2.         int hash = key.hashCode();
  3.         int index = hash & (table.length - 1);
  4.         if (table[index] == null) {
  5.             table[index] = new Entry(hash, key, value);
  6.         } else {
  7.             Entry<K, V> p = table[index];
  8.             while (true) {
  9.                 if (p.key.equals(key)) {//键已经存在，将原来键的值覆盖
  10.                     p.value = value;
  11.                     return;
  12.                 }
  13.                 if (p.next == null) {//键不存在，插入
  14.                     break;
  15.                 }
  16.                 p = p.next;
  17.             }
  18.             p.next = new Entry<>(hash, key, value);
  19.         }
  20.         size++;
  21.         if (size >= threshold) {//检查数组长度是否超出最大数组长度，超出则扩容
  22.             resize();
  23.         }
  24.     }

细节：为什么根据hash&(数组长度-1)来确定键值对的位置？

其实hash&(数组长度-1)等价于hash%数组长度，在数组长度为2^n的前提下

我们来看个例子：

十进制下：15%2=1

转化为二进制为：0001111%0000010=0000001

十进制下：15%4=3

转化为二进制为：0001111%0000100=0000011

十进制下：15%8=7

转化为二进制为：0001111%0001000=0000111

我们发现余数就是被除数保留的位数

因此为了提高运算的性能，我们可以对被除数进行&操作

0001111%0000010↔0001111&0000001=0000001

其中0000001为2^1-1

0001111%0000100↔0001111&0000011=0000011

0000011为2^2-1

那么综上：在数组长度为2^n的前提下，hash&(数组长度-1)等价于hash%数组长度

⑶扩容resize

bd8c70caa464449589a45a80f3875cb7.png

扩容的新数组容量为原来数组的2倍，扩容后我们要将数组每一位的键值对链表重装为两组

我们利用尾插法，若hash&数组长度==0则为一组，若hash&数组长度！=0则为另一组，最后我们将两组链表分装为2组

  1. private void resize() {
  2.         Entry[] newtable = new Entry[table.length * 2];//扩容容量为原来数组的两倍
  3.         for (int i = 0; i < table.length; i++) {
  4.             Entry<K, V> p = table[i];//获取每一个位置的链表拆分为两部分进行重装
  5.             if (p != null) {
  6.                 //尾查法
  7.                 Entry<K, V> a = null;//链表尾指针
  8.                 Entry<K, V> b = null;
  9.                 Entry<K, V> heada = null;//链表头指针，用来记录操作的链表
  10.                 Entry<K, V> headb = null;
  11.                 while (p != null) {
  12.                     //第一组：hash&数组长度==0   第二组：hash&数组长度！=0
  13.                     if ((p.hash & table.length) == 0) {
  14.                         if (a == null) {//刚开始添加，记录头指针
  15.                             heada = p;
  16.                         } else {
  17.                             a.next = p;
  18.                         }
  19.                         a = p;//尾指针后移
  20.                     } else {
  21.                         if (b == null) {//刚开始添加
  22.                             headb = p;
  23.                         } else {
  24.                             b.next = p;
  25.                         }
  26.                         b = p;//尾指针后移
  27.                     }
  28.                     p = p.next;
  29.                 }
  30.                 if (a != null) {//将尾指针指向null
  31.                     a.next = null;
  32.                     newtable[i] = heada;//将重装的链表分装到数组中
  33.                 }
  34.                 if (b != null) {
  35.                     b.next = null;
  36.                     newtable[i + table.length] = headb;
  37.                 }
  38.             }
  39.         }
  40.         table = newtable;//覆盖原来的数组
  41.         //更新最大数组长度
  42.         threshold = (int) (table.length * DEFAULT_LOAD_FACTOR);
  43.     }

细节：为什么要根据hash&数组长度进行分组？

我们来看一个例子：在数组长度为2^n前提下

十进制下：2%4=2

6%4=2

二进制下：0000010%0000100=0000010

0000110%0000100=0000010

我们进行&操作，检查倒数第三位，按位与后若结果为0则为一组，否则为另一组

⑷删除remove

删除操作与链表的删除操作相似

  1. public V remove(K key) {
  2.         int hash = key.hashCode();
  3.         int index = hash & (table.length - 1);//位置
  4.         if (table[index] == null) {
  5.             return null;
  6.         } else {
  7.             Entry<K, V> p = table[index];
  8.             Entry<K, V> pre = null;
  9.             //遍历链表寻找要删除的键值对
  10.             while (p != null) {
  11.                 if (p.key.equals(key)) {
  12.                     if (pre == null) {//链表头部元素
  13.                         table[index] = p.next;
  14.                     } else {
  15.                         pre.next = p.next;
  16.                     }
  17.                     size--;
  18.                     return p.value;
  19.                 }
  20.                 pre = p;
  21.                 p = p.next;
  22.             }
  23.         }
  24.         return null;
  25.     }

⑸获取get

  1. public V get(K key) {/**找对应键的值*/
  2.         int hash = key.hashCode();
  3.         //根据哈希值计算在数组中的位置
  4.         int index = hash & (table.length - 1);//hash%table.length;
  5.         if (table[index] == null) {
  6.             return null;
  7.         }
  8.         Entry<K, V> p = table[index];
  9.         //遍历链表，找到键对应的值
  10.         while (p != null) {
  11.             if (p.key.equals(key)) {
  12.                 return p.value;
  13.             }
  14.             p = p.next;
  15.         }
  16.         return null;

下面是我们实现的哈希表的完整的代码

  1. package myHashMap;
  2.  
  3. import java.util.Objects;
  4. import java.util.StringJoiner;
  5.  
  6. public class MyHashMap<K, V> {
  7.     static class Entry<K, V> {
  8.         /**
  9.          * 键值对
  10.          */
  11.         final int hash;//键的哈希值
  12.         final K key;//键唯一
  13.         V value;//值
  14.         Entry<K, V> next;//哈希值冲突的键值对用链表连接
  15.         public Entry(int hash, K key, V value) {
  16.             this.hash = hash;
  17.             this.key = key;
  18.             this.value = value;
  19.         }
  20.         @Override
  21.         public boolean equals(Object o) {
  22.             if (this == o) return true;//地址值相同
  23.             if (o == null || getClass() != o.getClass()) return false;//地址值不同
  24.             Entry<?, ?> entry = (Entry<?, ?>) o;
  25.             return Objects.equals(key, entry.key);
  26.         }
  27.         @Override
  28.         public final int hashCode() {
  29.             return Objects.hashCode(key) ^ Objects.hashCode(value);
  30.         }
  31.         @Override
  32.         public String toString() {
  33.             return key+"="+value;
  34.         }
  35.     }
  36.     Entry[] table = new Entry[16];//初始数组长度
  37.     int size = 0;//已存数组长度
  38.     final double DEFAULT_LOAD_FACTOR = 0.75d;//加载因子
  39.     int threshold = (int) (table.length * DEFAULT_LOAD_FACTOR);//可存入的最大数组长度
  40.     public MyHashMap() {}
  41.     public V get(K key) {/**找对应键的值*/
  42.         int hash = key.hashCode();
  43.         //根据哈希值计算在数组中的位置
  44.         int index = hash & (table.length - 1);//hash%table.length;
  45.         if (table[index] == null) {
  46.             return null;
  47.         }
  48.         Entry<K, V> p = table[index];
  49.         //遍历链表，找到键对应的值
  50.         while (p != null) {
  51.             if (p.key.equals(key)) {
  52.                 return p.value;
  53.             }
  54.             p = p.next;
  55.         }
  56.         return null;
  57.     }
  58.     public void put(K key, V value) {
  59.         int hash = key.hashCode();
  60.         int index = hash & (table.length - 1);
  61.         if (table[index] == null) {
  62.             table[index] = new Entry(hash, key, value);
  63.         } else {
  64.             Entry<K, V> p = table[index];
  65.             while (true) {
  66.                 if (p.key.equals(key)) {//键已经存在，将原来键的值覆盖
  67.                     p.value = value;
  68.                     return;
  69.                 }
  70.                 if (p.next == null) {//键不存在，插入
  71.                     break;
  72.                 }
  73.                 p = p.next;
  74.             }
  75.             p.next = new Entry<>(hash, key, value);
  76.         }
  77.         size++;
  78.         if (size >= threshold) {//检查数组长度是否超出最大数组长度，超出则扩容
  79.             resize();
  80.         }
  81.     }
  82.     private void resize() {
  83.         Entry[] newtable = new Entry[table.length * 2];//扩容容量为原来数组的两倍
  84.         for (int i = 0; i < table.length; i++) {
  85.             Entry<K, V> p = table[i];//获取每一个位置的链表拆分为两部分进行重装
  86.             if (p != null) {
  87.                 //尾查法
  88.                 Entry<K, V> a = null;//链表尾指针
  89.                 Entry<K, V> b = null;
  90.                 Entry<K, V> heada = null;//链表头指针，用来记录操作的链表
  91.                 Entry<K, V> headb = null;
  92.                 while (p != null) {
  93.                     //第一组：hash&数组长度==0   第二组：hash&数组长度！=0
  94.                     if ((p.hash & table.length) == 0) {
  95.                         if (a == null) {//刚开始添加，记录头指针
  96.                             heada = p;
  97.                         } else {
  98.                             a.next = p;
  99.                         }
  100.                         a = p;//尾指针后移
  101.                     } else {
  102.                         if (b == null) {//刚开始添加
  103.                             headb = p;
  104.                         } else {
  105.                             b.next = p;
  106.                         }
  107.                         b = p;//尾指针后移
  108.                     }
  109.                     p = p.next;
  110.                 }
  111.                 if (a != null) {//将尾指针指向null
  112.                     a.next = null;
  113.                     newtable[i] = heada;//将重装的链表分装到数组中
  114.                 }
  115.                 if (b != null) {
  116.                     b.next = null;
  117.                     newtable[i + table.length] = headb;
  118.                 }
  119.             }
  120.         }
  121.         table = newtable;//覆盖原来的数组
  122.         //更新最大数组长度
  123.         threshold = (int) (table.length * DEFAULT_LOAD_FACTOR);
  124.     }
  125.     @Override
  126.     public String toString() {
  127.         StringJoiner sj = new StringJoiner(",", "[", "]");
  128.         for (int i = 0; i < table.length; i++) {
  129.             Entry<K, V> p = table[i];
  130.             while (p != null) {
  131.                 sj.add(p.toString());
  132.                 p = p.next;
  133.             }
  134.         }
  135.         return sj.toString();
  136.     }
  137.     public V remove(K key) {
  138.         int hash = key.hashCode();
  139.         int index = hash & (table.length - 1);//位置
  140.         if (table[index] == null) {
  141.             return null;
  142.         } else {
  143.             Entry<K, V> p = table[index];
  144.             Entry<K, V> pre = null;
  145.             //遍历链表寻找要删除的键值对
  146.             while (p != null) {
  147.                 if (p.key.equals(key)) {
  148.                     if (pre == null) {//链表头部元素
  149.                         table[index] = p.next;
  150.                     } else {
  151.                         pre.next = p.next;
  152.                     }
  153.                     size--;
  154.                     return p.value;
  155.                 }
  156.                 pre = p;
  157.                 p = p.next;
  158.             }
  159.         }
  160.         return null;
  161.     }
  162. }

实现完成后我们来运行代码来爽一下吧

首先我们来看一下put方法的添加以及覆盖能否实现

  1.         MyHashMap<String,Integer> ha=new MyHashMap<>();
  2.         ha.put("aa",1);
  3.         ha.put("aa",5);
  4.         System.out.println(ha);//[aa=5]

然后是数组的扩容操作

1bc3f959385944c494bf5f71b7f526c7.png

79655650525942618b03d5b6f2086c8f.png

最后是remove以及get方法

6111776e5dde44c394995ae322558ec7.png

e569176220c64603ab6da2d820288c3c.png

四. 哈希表常见算法题

  在算法练习中，熟练的运用哈希表可以使许多题目简单很多，下面我整理了一些力扣中的有关哈希表的经典算法题，希望会对各位有所帮助

常见的利用哈希表主要有三种题型

①数组哈希

②set哈希

③map哈希

2ca042f8e5aa461a9c2df3d4c9e12a74.jpg

   若有不足，错误之处，望指出更正(*´I`*)

 

 

 

 

 

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号