当前位置:   article > 正文

Java实现数据结构---哈希表_java中新建哈希表

java中新建哈希表

哈希表简介

  1. 哈希表(Hash Table)也称为散列表,是一种根据关键字值(key - value)而直接访问的数据结构。它的底层是基于数组实现,通过对键值对的key进行Hash求值(哈希化)算出对应的数组下标索引,因此不需要遍历整个底层数组,插入删除效率均很快,被广泛应用。
  2. 哈希表的核心:哈希化时的算法,当多个key值哈希化后值相等时解决冲突的方法。

哈希函数与冲突

哈希函数

哈希函数就是利用一定的算法,对存储数据value进行一系列计算,求出对应数组索引下标值,然后将value值放在对应索引的数组中。

冲突

当两个不同的value值,利用哈希算法后得到了相同的索引值,但是改索引值只能存储一个数据,这种情况就是冲突。例如下面的情况:
在这里插入图片描述
冲突可能会导致哈希化方案无法实施,上面例子中:将50个数放到容量为60的数组中,因此在发生冲突时候,可以将后面添加的数据放入另外索引数据项中,这种方法称为开放地址法(开放地址法一般有三种方案:线性探测,二次探测,再哈希)。
另一种方法,就是数组的每个数据项都创建一个子链表或子数组,那么数组内不直接存放数据,当产生冲突时,新的数据项直接存放到这个数组下标表示的链表中,这种方法称为链地址法

开放地址法

线性探测

  • 线性探测原理是:在遇到冲突时,指针继续向哈希值索引下一个索引移动,直到遇到空的数据项时,将要填加的数据放入空数据项其中。
  • 哈希表变得太满时,我们如果想扩展数组容量,数据项不能放到新数组中和老数组相同索引的位置,而是要根据数组大小重新定义哈希函数计算插入位置。这个过程开销较大,所以一般我们要确定数据的范围,给定好数组的大小,就不再扩容

实现类:

	package com.xxliao.datastructure.linerar_list.hash_table.openness_address.linear_detection;

/**
 * @author xxliao
 * @description: 线性探测 实现哈希表
 * @date 2024/5/28 18:34
 */
public class HashTable {

    // hash数组
    private Integer[] array;

    // 数组容量
    private int capacity;
    // 数组中元素个数
    private int size;

    /** 构造函数*/
    public HashTable(int capacity) {
        array = new Integer[capacity];
        this.capacity = capacity;
    }

    /** 对数据项进行hash化,为了简单:对容量取余*/
    public int hash(Integer value) {

        return value % capacity;
    }

    /** 判断是否满了*/
    public boolean isFull() {

        return (size == capacity);
    }

    /** 判断是否为空*/
    public boolean isEmpty() {

        return (size == 0);
    }

    /** 添加数据*/
    public void insert(Integer value) {
        if(isFull()) {
            System.out.println("Table is full,Expansion");
            expansion();
        }
        int key = hash(value);
        while(array[key] != null) {
            // 指针下移
            key++;
            // 对key重新取余,防止key大于容量情况出现
            key = key % capacity;
        }
        array[key] = value;
        size++;
    }

    /** 删除数据*/
    public boolean remove(Integer value) {
        if(isEmpty()) {
            System.out.println("Table is Empty,Can't remove");
            return false;
        }
        int key = hash(value);
        while(array[key] != null) {
            if(array[key] == value) {
                //找到删除项
                array[key] = null;
                size--;
                return true;
            }
            key++;
            key = key % capacity;
        }
        return false;
    }

    /** 查找数据,判断是否存在*/
    public boolean find(Integer value) {
        if(isEmpty()) {
            System.out.println("Table is Empty");
            return false;
        }
        int key = hash(value);
        while(array[key] != null) {
            if(array[key] == value) {
                return true;
            }
            key++;
            key = key % capacity;
        }
        return false;
    }

    /** 数组扩容,原数据放入新数组时重新进行Hash计算*/
    private void expansion() {
        //  记录原数据
        Integer [] oldArray = array;
        //  数据个数清零
        size = 0;
        //  扩容
        capacity = capacity +  (capacity >> 1);
        array = new Integer[capacity];
        // 迁移原数据
        for(int i=0; i<oldArray.length; i++) {
            insert(oldArray[i]);
        }

    }

    /** 打印数据数据*/
    public void print(){
        System.out.print("Table:");
        for(int j = 0 ; j < capacity ; j++){
            if(array[j] != null){
                System.out.print(array[j] + " ");
            }else{
                System.out.print("** ");
            }
        }
        System.out.println();
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124

测试类:

package com.xxliao.datastructure.linerar_list.hash_table.openness_address.linear_detection;

/**
 * @author xxliao
 * @description: 线性探测实现哈希表 测试客户端
 * @date 2024/5/28 18:40
 */

public class TestClient {
    public static void main(String[] args) {
        // 数据源,17个数据,
        Integer [] array = {3,4,5,3,6,8,9,7,1,2,11,12,14,17,15,13,20};
        // 哈希表,初始长度为10
        HashTable hashTable = new HashTable(10);
        // 添加数据
        for(int i=0; i<array.length; i++) {
            hashTable.insert(array[i]);
        }
        // 打印数据
        hashTable.print();
        //删除数据 15,17,20
        hashTable.remove(15);
        hashTable.remove(17);
        hashTable.remove(20);
        // 打印数据
        hashTable.print();
    }
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

测试结果:
在这里插入图片描述

线性探测缺点

线性探测是在原索引的基础上一步一步向下移动索引,容易造成数据堆集在一个区域,后续添加数据与应该插入的位置错位,会形成数据的聚集,这里我们称之为原始聚集,从而失去了哈希表插入、查询快的优点。在这里插入图片描述

二次探测

相对于线性探测冲突时,让索引一步一步向下移动,二次探测的原理是:发生冲突时,跳跃式向下移动,比如第一次冲突移动1的平方、第二次冲突移动2的平方、第三次冲突移动3的平方、第四次冲突移动4的平方…,这样就可以有效的避免原始聚集,但是因为还是向下移动索引,还是不可避免某些情况下会再次形成聚集,这种聚集称之为二次聚集。因二次探测用的比较少,代码省略。

再哈希

为了消除原始聚集以及二次聚集,我们可以考虑发生冲突时候不是乡下移动指针,而是再次对插入值进行哈希,再次获取目标索引,这就是再哈希法。

这种方法使用两个散列函数 h1 和 h2。其中 h1 以关键字为自变量,产生一个 0 至 m-1 之间的数作为散列地址;h2 也以关键字为自变量,产生一个 1 至 m-1 之间的并和 m 互素的数(即 m 不能被该数整除)作为探查序列的地址增量(即步长)。这样做是使探查序列能够分布在整个 Hash 表。

链地址法

链地址法(Separate Chaining)的思路是将哈希值相同的元素构建成一个同义词的单项链表,并将单项链表的头节点存放在Hash数组中, 插入/查找/删除都在链表中进行.

结构大致如图:
在这里插入图片描述
下面是具体代码实现

链地址实现哈希表 节点类:

package com.xxliao.datastructure.linerar_list.hash_table.linked_address;

/**
 * @author xxliao
 * @description: 链地址实现哈希表 节点类
 * @date 2024/5/28 18:58
 */
public class Node {

    String key;
    String value;
    // 指向下一个结点
    Node next;

    public Node(String key, String value, Node next) {
        this.key = key;
        this.value = value;
        this.next = next;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

链地址实现哈希表 单链表类:

package com.xxliao.datastructure.linerar_list.hash_table.linked_address;

/**
 * @author xxliao
 * @description: 链地址实现哈希表 单链表类
 * @date 2024/5/28 18:59
 */
public class LinkedList {

    Node head; //头结点

    /**
     * 添加单链表结点
     *
     * @param key
     * @param value
     */
    public void addNode(String key, String value) {
        //在外界设置好head了
        if (head == null) return;
        // 创建结点
        Node node = new Node(key, value, null);
        // 临时变量
        Node tmp = head;
        //循环单链表
        while (true) {
            //key相同覆盖值 从head开始
            if (key.equals(tmp.key)) {
                tmp.value = value;
            }
            if (tmp.next == null) {
                break;
            }
            //指向下一个
            tmp = tmp.next;
        }
        //在循环外挂载最后一个结点
        tmp.next = node;
    }

    /**
     * 获得值
     *
     * @param key
     * @return
     */
    public String getVal(String key) {
        if (head == null) return null;
        //只有一个结点
        if (head.next == null) {
            return head.value;
        }
        //遍历单链表
        else {
            Node tmp = head;
            while (tmp != null) {
                //找到匹配的key
                if (key.equals(tmp.key)) {
                    return tmp.value;
                }
                //指向下一个
                tmp = tmp.next;
            }
            return null;
        }
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67

链地址实现哈希表 实现类:

package com.xxliao.datastructure.linerar_list.hash_table.linked_address;

/**
 * @author xxliao
 * @description: 链地址实现哈希表
 * @date 2024/5/28 19:08
 */

public class CustomHashMap {
    //数组初始化 2的n次方
    LinkedList[] map=new LinkedList[8];
    //ListNode的个数
    int size;
    /**
     * 设置值
     * @param key
     * @param value
     */
    public void put(String key,String value){
        //该扩容了
        if(size>=map.length*0.75){
            System.out.println("map需要扩容");
            return;
        }
        //计算索引 数组下标
        int index=Math.abs(key.hashCode())%map.length;
        //获得该下标处的ListNode
        LinkedList ln=map[index];
        //该下标处无值
        if(ln==null){
            //创建单链表
            LinkedList lnNew=new LinkedList();
            //创建头结点
            Node head=new Node(key,value,null);
            //挂载头结点
            lnNew.head=head;
            //把单链放到数组里
            map[index]=lnNew;
            size++;
        }
        //该下标有值,hash碰撞
        else {
            //单链表挂结点
            ln.addNode(key,value);
        }
    }
    /**
     * 取值
     * @param key
     * @return
     */
    public String get(String key){
        int index=Math.abs(key.hashCode())%map.length;
        LinkedList ln=map[index];
        if(ln==null) return null;
        return ln.getVal(key);
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59

测试类:

package com.xxliao.datastructure.linerar_list.hash_table.linked_address;

/**
 * @author xxliao
 * @description: 链地址实现哈希表 测试客户端
 * @date 2024/5/28 19:12
 */

public class TestClient {

    public static void main(String[] args) {
        CustomHashMap hashMap=new CustomHashMap();
        hashMap.put("m3","m3m3");
        hashMap.put("c1","c1c1");
        hashMap.put("c1","cc11");
        System.out.println(hashMap.get("c1"));
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

测试结果:
在这里插入图片描述

完整代码

https://github.com/xxliao100/datastructure_algorithms.git

声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号