当前位置: 首页 > news >正文

数据结构与算法——(Hash)哈希表与哈希算法

1.哈希表

在这里插入图片描述

给每份数据分配一个编号,放入表格(数组)
建立编号与表格索引的关系,将来就可以通过编号快速查找数据

  1. 理想情况编号当唯一,表格能容纳所有数据
  2. 现实是不能说为了容纳所有数据造一个超大表格,编号也有可能重复

解决方案

  1. 有限长度的数组,以拉链方式存储数据
  2. 允许编号适当重复,通过数据自身来进行区分

在这里插入图片描述
代码(不包含扩容)

public class HashTable<K extends Comparable<K>, V> {private Entry<K, V>[] table = new Entry[16];//这个数组里存放链表的头节点,初始容量为16private int size;//哈希表中元素个数,初始值为0//获取值public V get(int hash, K key) {/*** 求模运算替换为位运算* 前提:*      1.数组长度是2的n次方*      2.hash % table.length 等价于 hash & (table.length - 1)*///1.根据hash获取该数据在数组中的位置int index = hash & (table.length - 1);//2.获取链表的头节点Entry<K, V> entry = table[index];while (entry != null) {if (key.compareTo(entry.key) == 0) {return entry.value;}entry = entry.next;}return null;}//添加,key存在就修改,否则添加public void put(int hash, K key, V value) {//1.根据hash获取该数据在数组中的位置int index = hash & (table.length - 1);//2.判断链表中是否有这个key,有则替换Entry<K, V> entry = table[index];Entry<K, V> parent = null;while (entry != null) {parent = entry;if (key.compareTo(entry.key) == 0) {entry.value = value;return;}entry = entry.next;}//3.需要新增Entry<K, V> add = new Entry<>(hash, key, value);if (parent == null) {table[index] = add;} else {parent.next = add;}//4.修改长度size++;}//删除public V remove(int hash, K key) {int index = hash & (table.length - 1);Entry<K, V> entry = table[index];if (entry == null) {return null;}Entry<K, V> prev = null;//上一节点while (entry != null) {if (key.compareTo(entry.key) == 0) {if (prev == null) {table[index] = entry.next;} else {prev.next = entry.next;}size--;return entry.value;}prev = entry;entry = entry.next;}return null;}//定义节点类private static class Entry<K extends Comparable<K>, V> {private int hash;//哈希码private K key;//键private V value;//值private Entry<K, V> next;//下一个链表public Entry(int hash, K key, V value) {this.hash = hash;this.key = key;this.value = value;}}
}

扩容

负载因子: l o a d f a c t o r ( α ) = n m load factor(α) = \frac{n}{m} loadfactor(α)=mn ,n表示hash表中元素的个数,m表示hash表数组的长度,在Java中的取值是 0.75

在这里插入图片描述

扩容代码

public class HashTable<K extends Comparable<K>, V> {private Entry<K, V>[] table = new Entry[16];//这个数组里存放链表的头节点,初始容量为16private int size;//哈希表中元素个数,初始值为0private float loadFactor = 0.75f;//负载因子,在Java中是 0.75private int threshold = (int) (loadFactor * table.length);//预值,也就是当数组长度达到 12的时候进行扩容//扩容方法private void resize() {//1.扩容一倍Entry<K, V>[] newTable = new Entry[table.length << 1];for (int i = 0; i < table.length; i++) {//2.获取每个链表的头节点,把链表进行拆分 a 和 bEntry<K, V> p = table[i];if (p != null) {/*** 拆分链表规律* hash & (table.length - 1) == 0 分为一组* hash & (table.length - 1) != 0 分为一组** 例如:*      0->8->16->24->32->40->48->56->64->72->80->null*      p**      a:0->16->32->48->64->80->null**      b:8->24->40->56->72->null*/Entry<K, V> aHead = null;Entry<K, V> bHead = null;Entry<K, V> a = null;Entry<K, V> b = null;while (p != null) {if ((p.hash & (table.length)) == 0) {//分配给aif (a != null) {a.next = p;} else {aHead = p;}a = p;} else {//分配给bif (b != null) {b.next = p;} else {bHead = p;}b = p;}p = p.next;}if (a != null) {a.next = null;table[i] = aHead;//放在原来的数组位置}if (b != null) {b.next = null;table[i + table.length] = bHead;}}}table = newTable;threshold = (int) (loadFactor * table.length);//预值}//定义节点类private static class Entry<K extends Comparable<K>, V> {private int hash;//哈希码private K key;//键private V value;//值private Entry<K, V> next;//下一个链表public Entry(int hash, K key, V value) {this.hash = hash;this.key = key;this.value = value;}}
}

问题总结
前提:数组长度是 2 的 n 次方

  1. 为什么计算索引位置用式子:hash & (数组长度-1)
    - hash & (数组长度-1) 等价于 hash % 数组长度
  2. 为什么旧链表会拆分成两条,一条 hash & 旧数组长度 == 0,另一条 != 0
    - 旧数组长度换算成二进制后,其中的 1 就是我们要检查的倒数第几位
    - hash & 8,8的二进制是 1000

2.哈希算法

1.概述

哈希算法(Hash Algorithm)是一种将任意长度的输入(称为预映射或消息)转换成固定长度输出(称为哈希值或散列值)的函数。哈希值通常是一个较短的、固定长度的数字串,它几乎唯一地对应于原始数据。

2.特点
  1. 确定性:相同的输入总是产生相同的哈希值。
  2. 不可逆性:从哈希值很难反推出原始输入数据。
  3. 雪崩效应:输入数据的微小变化会导致哈希值的显著不同。
  4. 抗碰撞性:找到两个不同的输入产生相同哈希值的难度非常高。
3.Object.hashCode()
  • Object 的 hashCode 方法默认是生成随机数作为 hash 值(会缓存在对象头当中)
  • 缺点是包含相同的不同对象,他们的 hashCode 不一样,不能够用 hash 值来反映对象的特征,因此诸多子类都会重写 hashCode 方法

在这里插入图片描述
在这里插入图片描述
结论:同一对象的hashCode相同

4.String.hashCode()

在这里插入图片描述
结论:相同值不同对象的hashCode相同
String对象的hashCode怎么实现的呢???

public class HashCode {public static void main(String[] args) {String s1 = "abc";int hash = 0;for (int i = 0; i < s1.length(); i++) {int code = s1.charAt(i);hash = 10 * hash + code;//对于 abc : a * 100 + b * 10 + c}System.out.println(hash);//10779}
}

如果把倍数改成31(一个质数)

在这里插入图片描述

完整代码

public class HashTable<K extends Comparable<K>, V> {private Entry<K, V>[] table = new Entry[16];//这个数组里存放链表的头节点,初始容量为16private int size;//哈希表中元素个数,初始值为0private float loadFactor = 0.75f;//负载因子,在Java中是 0.75private int threshold = (int) (loadFactor * table.length);//预值,也就是当数组长度达到 12的时候进行扩容//获取值private V get(int hash, K key) {/*** 求模运算替换为位运算* 前提:*      1.数组长度是2的n次方*      2.hash % table.length 等价于 hash & (table.length - 1)*///1.根据hash获取该数据在数组中的位置int index = hash & (table.length - 1);//2.获取链表的头节点Entry<K, V> entry = table[index];while (entry != null) {if (key.compareTo(entry.key) == 0) {return entry.value;}entry = entry.next;}return null;}//获取值public V get(K key) {return get(hash(key), key);}//添加,key存在就修改,否则添加private void put(int hash, K key, V value) {//1.根据hash获取该数据在数组中的位置int index = hash & (table.length - 1);//2.判断链表中是否有这个key,有则替换Entry<K, V> entry = table[index];Entry<K, V> parent = null;while (entry != null) {parent = entry;if (key.compareTo(entry.key) == 0) {entry.value = value;return;}entry = entry.next;}//3.需要新增Entry<K, V> add = new Entry<>(hash, key, value);if (parent == null) {table[index] = add;} else {parent.next = add;}//4.修改长度size++;//5.当数据长度达到预值时进行扩容if (size > threshold) {resize();}}//添加,key存在就修改,否则添加public void put(K key, V value) {put(hash(key), key, value);}//删除private V remove(int hash, K key) {int index = hash & (table.length - 1);Entry<K, V> entry = table[index];if (entry == null) {return null;}Entry<K, V> prev = null;//上一节点while (entry != null) {if (key.compareTo(entry.key) == 0) {if (prev == null) {table[index] = entry.next;} else {prev.next = entry.next;}size--;return entry.value;}prev = entry;entry = entry.next;}return null;}//删除public V remove(K key) {return remove(hash(key), key);}//根据key获取hashCodeprivate int hash(K key) {if (key instanceof String k) {return k.hashCode();}int hash = key.hashCode();return hash ^ (hash >>> 16);}//扩容方法private void resize() {//1.扩容一倍Entry<K, V>[] newTable = new Entry[table.length << 1];for (int i = 0; i < table.length; i++) {//2.获取每个链表的头节点,把链表进行拆分 a 和 bEntry<K, V> p = table[i];if (p != null) {/*** 拆分链表规律* hash & (table.length - 1) == 0 分为一组* hash & (table.length - 1) != 0 分为一组** 例如:*      0->8->16->24->32->40->48->56->64->72->80->null*      p**      a:0->16->32->48->64->80->null**      b:8->24->40->56->72->null*/Entry<K, V> aHead = null;Entry<K, V> bHead = null;Entry<K, V> a = null;Entry<K, V> b = null;while (p != null) {if ((p.hash & (table.length)) == 0) {//分配给aif (a != null) {a.next = p;} else {aHead = p;}a = p;} else {//分配给bif (b != null) {b.next = p;} else {bHead = p;}b = p;}p = p.next;}if (a != null) {a.next = null;table[i] = aHead;//放在原来的数组位置}if (b != null) {b.next = null;table[i + table.length] = bHead;}}}table = newTable;threshold = (int) (loadFactor * table.length);//预值}//定义节点类private static class Entry<K extends Comparable<K>, V> {private int hash;//哈希码private K key;//键private V value;//值private Entry<K, V> next;//下一个链表public Entry(int hash, K key, V value) {this.hash = hash;this.key = key;this.value = value;}}
}

LeetCode题目

1题
3题
49题
217题
136题
242题
387题
819题


http://www.mrgr.cn/news/61922.html

相关文章:

  • 说一说QWidget
  • 刷代随有感(134):单调栈——下一个更大元素I(难点涉及哈希表与单调栈的结合)
  • libavdevice.so.58: cannot open shared object file: No such file ordirectory踩坑
  • vue3中ref和reactive的用法,区别和优缺点,以及使用场景
  • Mac打开环境变量配置文件,source ~/.zshrc无法打开问题解决
  • 浅谈人工智能之基于LLaMA-Factory进行Qwen2微调:医疗大模型
  • 【生物学&水族馆】金鱼成体幼苗检测活体识别系统源码&数据集全套:改进yolo11-Parc
  • 打工人不上班之后,躺平还是躺赢?
  • 数据结构和算法-动态规划(3)-经典问题
  • 自闭症摘帽:突破束缚的新方式
  • YOLO即插即用模块--PPA
  • 【LeetCode】两数之和、大数相加
  • Brainpy的jit编译环境基础
  • Linux_02 Linux常用软件——vi、vim
  • 【算法】(Python)回溯算法
  • Spring Cloud Ribbon:负载均衡的服务调用
  • Java 泛型和反射(15/30)
  • 软件工程经验详细总结
  • 进程线程、同步异步、并发并行
  • 小游戏发展迅速,游戏平台如何从技术方向加速业务转化?
  • 如何进行Java的时间序列分析与算法优化,应该从何入手?
  • 大模型:索引构建、预检索与检索阶段、检索后与生成阶段
  • 自动批量生成图片代码
  • Apache Hive 通过Docker快速入门
  • 深入解析Sysmon日志:增强网络安全与威胁应对的关键一环
  • Leetcode—3216. 交换后字典序最小的字符串【简单】