手写哈希表

梁霖编程工具库 2023-01-07

303

背景

查找算法不论是顺序查找还是二分查找，其查找的过程中都需要进行若干次的比较，比如顺序查找需要经过n次的比较，二分查找需要经过logn次的比较，那么有没有什么数据结构可以保证1次比较或者只需要几次比较就可以判断是否能找到这样的元素呢？这种数据结构就是hash表。

什么是哈希表

哈希表又称为散列表，它是一种以键值对形式来存储数据的结构，只要输入待查找的key，就可以通过该key寻找到对应的值。
哈希表用的是数据支持下标随机访问数据的特性来实现的，所以说哈希表是数组的扩展，是由数据演化而成。

哈希表的新增操作

可以通过mod运算来算出数据应该存放到哈希表的哪个位置
比如key=19，value=40，hash表的表长是length=13，那么key % length = 6 ，因此key=19这个元素应该放在哈希表下标为6的位置。

哈希表的查找操作

对于给定的key通过mod运算找出对应的位置，然后判断再这个位置上是否有元素，即可以判断是否找到对应的元素。

哈希冲突

在我们对哈希表执行新增操作的时候，如果有多个元素映射到同一个哈希表中的位置，那么就产生了哈希冲突，也称之为哈希碰撞。
比如在上图的哈希表中，我们再新增元素key=89，value=89，此时我们计算出映射下标idx = 1 ，但之前的idx=1的位置已经存放了key=12的元素，这时就产生了哈希冲突。

哈希冲突解决方法

线性探测法：当发生冲突以后，就顺次向后挪动，直到找到第一个没有冲突的位置就停止下来。

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

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

哈希表在有哈希冲突下的查询操作

首先我们需要计算出待查询元素位于哈希表的下标idx，如果下标idx元素为空，那么就认为找不到该元素
如果idx处不为空且结果不等于我们待查找的元素，应该按照哈希冲突的方法不断的挪动待查找的位置，直到找到元素或者遇到了第一个为空的位置就认为找不到元素。

哈希表在有哈希冲突下的删除操作

针对链地址法的哈希表，直接物理删除即可，因为物理删除不会引发歧义。
针对线性探测的哈希表和二次探测的哈希表，只能进行逻辑删除，即删除的时候做一个逻辑标记即可。如果直接物理删除，那么可能会导致后面待查询的元素明明在哈希表中，但却出现查询不到的情况。

评价哈希算法的指标

装载因子：实际存储的空间总存储空间
比如上图中装载因子 = 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"));
    }
}

文章转载自梁霖编程工具库，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

手写哈希表

评论