济南官方网站,手机访问另一部手机访问文件,做截图网官网,徐州网站建设魔站通常情况下哈希函数的输入空间远大于输出空间#xff0c;因此理论上哈希冲突是不可避免的。比如#xff0c;输入空间为全体整数#xff0c;输出空间为数组容量大小#xff0c;则必然有多个整数映射至同一数组索引。
解决哈希冲突方法常见有#xff1a;链地址法、开放寻址…通常情况下哈希函数的输入空间远大于输出空间因此理论上哈希冲突是不可避免的。比如输入空间为全体整数输出空间为数组容量大小则必然有多个整数映射至同一数组索引。
解决哈希冲突方法常见有链地址法、开放寻址法。
注意无论是开放寻址还是链地址法它们只能保证哈希表可以在发生冲突时正常工作但无法减少哈希冲突的发生。常见的哈希算法有DM5、sha-1、sha-2和sha-3。
在原始哈希表中每个桶仅能存储一个键值对。「链式地址 separate chaining」将单个元素转换为链表将键值对作为链表节点将所有发生冲突的键值对都存储在同一链表中。
package com.wei.mybatisflex.demo;import java.util.ArrayList;
import java.util.List;/*** 链式地址哈希表*/
public class HashMapChaining {int size; // 键值对数量int capacity; // 哈希表容量double loadThres; // 触发扩容的负载因子阈值(键值对数量/哈希表容量 标准为 0.75int extendRatio; // 扩容倍数ListListPair buckets; // 桶数组这里用动态数组ListPair代替链表一个桶就是一个链表。/*** 键值对定义*/class Pair{private int key;private String val;public Pair(int key, String val) {this.key key;this.val val;}}/* 构造方法 */public HashMapChaining() {size 0;capacity 4;loadThres 2 / 3.0;extendRatio 2;buckets new ArrayList(capacity);for (int i 0; i capacity; i) {buckets.add(new ArrayList());}}/* 哈希函数 */int hashFunc(int key) {return key % capacity;}/* 负载因子 */double loadFactor() {return (double) size / capacity;}/* 查询操作 */String get(int key) {int index hashFunc(key);ListPair bucket buckets.get(index);// 遍历桶若找到 key 则返回对应 valfor (Pair pair : bucket) {if (pair.key key) {return pair.val;}}// 若未找到 key 则返回 nullreturn null;}/* 添加操作 */void put(int key, String val) {// 当负载因子超过阈值时执行扩容if (loadFactor() loadThres) {extend();}int index hashFunc(key);ListPair bucket buckets.get(index);// 遍历桶若遇到指定 key 则更新对应 val 并返回for (Pair pair : bucket) {if (pair.key key) {pair.val val;return;}}// 若无该 key 则将键值对添加至尾部Pair pair new Pair(key, val);bucket.add(pair);size;}/* 删除操作 */void remove(int key) {int index hashFunc(key);ListPair bucket buckets.get(index);// 遍历桶从中删除键值对for (Pair pair : bucket) {if (pair.key key) {bucket.remove(pair);size--;break;}}}/* 扩容哈希表 */void extend() {// 暂存原哈希表ListListPair bucketsTmp buckets;// 初始化扩容后的新哈希表capacity * extendRatio;buckets new ArrayList(capacity);for (int i 0; i capacity; i) {buckets.add(new ArrayList());}size 0;// 将键值对从原哈希表搬运至新哈希表for (ListPair bucket : bucketsTmp) {for (Pair pair : bucket) {put(pair.key, pair.val);}}}/* 打印哈希表 */void print() {for (ListPair bucket : buckets) {ListString res new ArrayList();for (Pair pair : bucket) {res.add(pair.key - pair.val);}System.out.println(res);}}/*** 测试*/public static void main(String[] args) {HashMapChaining hashMapChaining new HashMapChaining();hashMapChaining.put(123, 23);hashMapChaining.put(124, 24);hashMapChaining.put(125, 25);hashMapChaining.put(126, 26);System.out.println(哈希表展示如下);hashMapChaining.print();System.out.println();String s hashMapChaining.get(123);System.out.println(k123对应的val值是s);System.out.println();hashMapChaining.put(124, 99);System.out.println(把key124的值换成99);hashMapChaining.print();System.out.println();hashMapChaining.remove(124);System.out.println(删除key124所对应的值);hashMapChaining.print();}
}
