手写哈希表

简介: 手写哈希表

公众号merlinsea


  • 背景
  • 查找算法不论是顺序查找还是二分查找,其查找的过程中都需要进行若干次的比较,比如顺序查找需要经过n次的比较,二分查找需要经过logn次的比较,那么有没有什么数据结构可以保证1次比较或者只需要几次比较就可以判断是否能找到这样的元素呢?这种数据结构就是hash表。
  • 什么是哈希表
  • 哈希表又称为散列表,它是一种以键值对形式来存储数据的结构,只要输入待查找的key,就可以通过该key寻找到对应的值。
  • 哈希表用的是数据支持下标随机访问数据的特性来实现的,所以说哈希表是数组的扩展,是由数据演化而成。
  • 哈希表的新增操作
  • 可以通过mod运算来算出数据应该存放到哈希表的哪个位置
  • 比如key=19,value=40,hash表的表长是length=13,那么key % length = 6  ,因此key=19这个元素应该放在哈希表下标为6的位置。


640.png


  • 哈希表的查找操作
  • 对于给定的key通过mod运算找出对应的位置,然后判断再这个位置上是否有元素,即可以判断是否找到对应的元素。
  • 哈希冲突
  • 在我们对哈希表执行新增操作的时候,如果有多个元素映射到同一个哈希表中的位置,那么就产生了哈希冲突,也称之为哈希碰撞。
  • 比如在上图的哈希表中,我们再新增元素key=89,value=89,此时我们计算出映射下标idx = 1 ,但之前的idx=1的位置已经存放了key=12的元素,这时就产生了哈希冲突。

640.png


  • 哈希冲突解决方法
  • 线性探测法:当发生冲突以后,就顺次向后挪动,直到找到第一个没有冲突的位置就停止下来。

640.png


  • 二次探测法:当发生冲突以后,按照先右后左的顺序摆动,直到找到第一个没有冲突的位置就停止下来。

640.png

  • 链地址法:基于链表的操作,来解决冲突问题, 当发生冲突以后,则把元素以链表的方法链接在对应的位置下面即可解决哈希冲突。

640.png

  • 哈希表在有哈希冲突下的查询操作
  • 首先我们需要计算出待查询元素位于哈希表的下标idx,如果下标idx元素为空,那么就认为找不到该元素
  • 如果idx处不为空且结果不等于我们待查找的元素,应该按照哈希冲突的方法不断的挪动待查找的位置,直到找到元素或者遇到了第一个为空的位置就认为找不到元素。
  • 哈希表在有哈希冲突下的删除操作
  • 针对链地址法的哈希表,直接物理删除即可,因为物理删除不会引发歧义。
  • 针对线性探测的哈希表和二次探测的哈希表,只能进行逻辑删除,即删除的时候做一个逻辑标记即可。如果直接物理删除,那么可能会导致后面待查询的元素明明在哈希表中,但却出现查询不到的情况。


640.png


  • 评价哈希算法的指标
  • 装载因子: 实际存储的空间 / 总存储空间
  • 比如上图中装载因子 = 5 / 11 = 0.456,装载因子越大越容易发生哈希冲突。
  • 手写实现一个以链表法解决冲突的哈希表
  • 需要注意的点:
  • 1、当实际装载的哈希槽超过了最大装载因子的容量需要考虑hash扩容
  • 2、当同一个槽中产生的hash冲突超过一定数量的时候,需要考虑链表转为红黑树
  • 3、哈希表的遍历时候,考虑实现一个迭代器
  • 定义链表的节点


public class Node {
    private String key;
    private String value;
    private int hash;
    private Node next;
    public Node(String key, String value, int hash, Node next) {
        this.key = key;
        this.value = value;
        this.hash = hash;
        this.next = next;
    }
    public Node() {
    }
    public void setValue(String val){
        this.value = val;
    }
    public String getKey(){
        return key;
    }
    public Node getNext(){
        return next;
    }
    public void setNext(Node next){
        this.next = next;
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (!(o instanceof Node)){
            return false;
        }
        Node node = (Node) o;
        return Objects.equals(key, node.key);
    }
    @Override
    public int hashCode() {
        return Objects.hash(key);
    }
    @Override
    public String toString() {
        return "Node{" +
                "key='" + key + '\'' +
                ", value='" + value + '\'' +
                ", hash=" + hash +
                '}';
    }
}


  • 定义哈希表    


public class MyHashTable {
    private Node[] table;
    private double loadFactor;
    private int size;
    private int availableBucket;
    // static 表示成员变量属于这个类
    private static final double default_load_factor = 0.75;
    private static final int default_capacity = 16;
    private static final int linkToTreeCount = 8;
    public MyHashTable(int capacity,double loadFactor){
        this.loadFactor = loadFactor;
        table = new Node[capacity];
        size = 0;
        availableBucket = 0;
    }
    public MyHashTable(){
        this(default_capacity,default_load_factor);
    }
    private int hash(String key){
        return Objects.hash(key);
    }
    public void output(){
        for(int i =0;i<table.length;i++){
            Node p = table[i];
            System.out.println("第 "+i+" 桶");
            while(p!=null){
                System.out.printf("%s\t",p.toString());
                p = p.getNext();
            }
            System.out.println();
        }
    }
    public Node get(String key){
        int hash = hash(key);
        int idx = (table.length-1)&hash;
        Node p = table[idx];
        while(p!=null && !p.getKey().equals(key)){
            p = p.getNext();
        }
        return p;
    }
    public boolean put(String key,String value){
        int hash = hash(key);
        int idx = (table.length-1)&hash;
//        if(table[idx] instanceof Node){
//
//        }else{
//            // 红黑树插入
//        }
        Node head = table[idx];
        if(head == null){
            table[idx] = new Node(key,value,hash,null);
            size++;
            availableBucket++;
        }else{
            Node p = head;
            Node tar = new Node(key,value,hash,null);
            Node tail = null;
            int linkLen = 0;
            while(p!=null){
                if(p.equals(tar)){
                    // 进行一个替换
                    p.setValue(value);
                    return false;
                }
                tail = p;
                p = p.getNext();
                linkLen++;
            }
            if(p==null){
                tail.setNext(tar);
                linkLen++;
            }
            if(linkLen > linkToTreeCount){
                // 链表转红黑树
                // link2tree();
            }
        }
        if(availableBucket >= (int)table.length*loadFactor){
            // 扩容
            // reszie();
        }
        return true;
    }
}


  • Main函数调用


public class Main {
    public static void main(String[] args) {
        MyHashTable table = new MyHashTable();
        table.put("123","1234");
        table.put("1234","12345");
        table.put("12","123");
        table.put("1","12");
        table.put("1235","123456");
        table.put("123456","1234567");
        table.put("123","321");
        table.output();
        System.out.println("get(123) = " +table.get("123"));
    }
}


目录
打赏
0
0
0
0
297
分享
相关文章
一文让你读懂Python中的Response对象
一文让你读懂Python中的Response对象
372 0
【合并两个有序数组】LeetCode第88题讲解
【合并两个有序数组】LeetCode第88题讲解
|
9月前
|
RSA加密算法详解与Python和Go实现
RSA加密算法详解与Python和Go实现
617 1
InnoDB与MyISAM实现索引方式的区别?
首先两者都是用的是B+树索引,但二者的实现方式不同。 对于主键索引,InnoDB中叶子节点保存了完整的数据记录,而MyISAM中索引文件与数据文件是分离的,叶子节点上的索引文件仅保存了数据记录的地址. 对于辅助索引,InnoDB中辅助索引会对主键进行存储,查找时,先通过辅助索引的B+树在叶子节点获取对应的主键,然后使用主键在主索引B+树上检索操作,最终得到行数据;MyISAM中要求主索引是唯一的,而辅助索引可以是重复的,主索引与辅助索引没有任何区别,因此,MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引,如果指定的Key存在,则取出其data域的值,然后以data域的值为地址
基于ssm+vue.js+uniapp小程序的反诈科普平台附带文章和源代码部署视频讲解等
基于ssm+vue.js+uniapp小程序的反诈科普平台附带文章和源代码部署视频讲解等
167 1
MinIO 客户端安装与使用教程
详细讲解MinIO CLI的安装与使用
4222 0
Bartender基本操作
本教程使用的是Bartender10,其他版本的Bartender使用上差不多。
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问