Java练习代码（四）- 简单哈希表实现

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Java练习代码（四）- 简单哈希表实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2777字，纯文字阅读大概需要4分钟。

内容图文

package Java2021_4_4;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @Create with IntelliJ IDEA
 * @Description :
 * @Auther : HMW
 * @Date: 2021-04-05
 * @Time: 12:12
 **/
public class HashMap {

    static class Node {
        public int key;
        public int value;

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", value=" + value +
                    '}';
        }
    }

    //创建一个数组， 存储list线性表存储， 里面存储的是linkedlist链表, 容量大小为101,下标范围[0,100]。可以取到100
    public LinkedList<Node>[] list = new LinkedList[3];
    public int size = 0;


    //模拟实现hashmap中插入，
    //实现方法为 - 在key哈希映射对应下标， 然后在下标对应的链表中查找
    //找到了（存在该key值）则进行修改value
    //没有找到（不存在该key值）则进行头插入该结点。

    public static double LOAD_FACTOR = 0.7;     //负载因子

    public boolean put(int key, int value) {
        //1. 通过哈希函数映射对应的下标
        int index = key % list.length;
        //2. 判断下标对应的链表是否存在
        LinkedList<Node> linkedList = list[index];
        if(linkedList == null) {
            list[index] = new LinkedList<>();
            list[index].addFirst(new Node(key, value));
            this.size++;
            return true;
        }
        //3. 判断该链表中是否存在该键值对
        for(Node it : linkedList) {
            if(it.key == key) {
                //存在该key值， 修改value
                it.value = value;
                return false;
            }
        }
        //出来证明不存在则插入
        linkedList.addFirst(new Node(key, value));
        this.size++;
        if(this.size / list.length > LOAD_FACTOR) {
            //超过负载因子， 需要扩容， 数据搬迁
            resize();
        }
        return true;
    }
    //扩容函数
    private void resize() {
        //容量扩展为原来的2倍
        LinkedList<Node>[] newArray = new LinkedList[2 * this.list.length];
        //遍历原来的list数组， 然后取到每一个元素，重新计算hash值，在新的数组重新插入
        for(int i = 0; i < this.list.length; i++) {
            LinkedList<Node> linkedList = this.list[i];
            if(linkedList == null) {
                //证明该位置目前还没有存放元素
                continue;
            }
            //for-each遍历链表
            for(Node it : linkedList) {
                int newIndex = it.key % newArray.length;
                if(newArray[newIndex] == null) {
                    //第一次插入元素
                    newArray[newIndex] = new LinkedList<>();
                    newArray[newIndex].addFirst(new Node(it.key, it.value));
                }
                else {
                    //不是第一次插入
                    newArray[newIndex].addFirst(new Node(it.key, it.value));
                }
            }
        }
        //让原来数组的引用指向新的数组的地址
        this.list = newArray;
    }

    //查找指定元素是否存在
    public boolean get(int key) {
        int index = key % list.length;
        if(list[index] == null) {
            return false;
        }

        LinkedList<Node> linkedList = list[index];
        for(Node node : linkedList) {
            if(node.key == key) {
                System.out.println(node);
                return true;
            }
        }
        return false;
    }

    //遍历哈希表
    public void print() {
        for(int i = 0; i < list.length; i++) {
            if(list[i] == null) {
                continue;
            }
            for(Node node : list[i]) {
                System.out.println(node);
            }
        }
    }

    public static void main(String[] args) {
        HashMap hashMap = new HashMap();


        hashMap.put(1,1);
        hashMap.put(2,2);
        hashMap.put(3,3);
        hashMap.put(4,4);


        hashMap.print();

        System.out.println(hashMap.get(0));

    }
}

内容总结

以上是互联网集市为您收集整理的Java练习代码（四）- 简单哈希表实现全部内容，希望文章能够帮你解决Java练习代码（四）- 简单哈希表实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端