精华内容
下载资源
问答
  • 哈希表java实现
    千次阅读
    2022-04-26 14:00:03

    哈希表也叫散列表,是根据关键码值(key-value)而进行直接访问的数据结构。它通过把关键码值映射到表中的某一位置来访问记录,这个映射函数叫做散列函数,存放记录的数组叫散列表。

    哈希表可以用数组+链表来实现,也可以用数组+树来实现。本例子用数组+链表来实现。散列函数直接用取余来完成。

    public class HashTable {
        private int size;
        private EmpLinkedList[] empLinkedList;
    
        public static void main(String[] args) {
            HashTable hashTable = new HashTable(8);
            Scanner scanner = new Scanner(System.in);
            String key = "";
            while (true) {
                System.out.println("欢迎使用散列表");
                System.out.println("新增职员:add");
                System.out.println("修改职员:update");
                System.out.println("查询职员:find");
                System.out.println("删除职员:remove");
                System.out.println("遍历职员:list");
                System.out.println("退出散列表:exit");
                key = scanner.next();
                switch (key) {
                    case "add": {
                        System.out.println("输入id");
                        int i = scanner.nextInt();
                        System.out.println("输入姓名");
                        String name = scanner.next();
                        Emp emp = new Emp(i, name);
                        hashTable.add(emp);
                        break;
                    }
                    case "update": {
                        System.out.println("输入id");
                        int i = scanner.nextInt();
                        System.out.println("输入姓名");
                        String name = scanner.next();
                        Emp emp = new Emp(i, name);
                        hashTable.update(emp);
                        break;
                    }
                    case "find": {
                        System.out.println("输入id");
                        int i = scanner.nextInt();
                        System.out.println(hashTable.findEmyById(i).name);
                        break;
                    }
                    case "remove": {
                        System.out.println("输入id");
                        int i = scanner.nextInt();
                        hashTable.removeById(i);
                        break;
                    }
                    case "list": {
                        hashTable.list();
                        break;
                    }
                    case "exit": {
                        scanner.close();
                        System.exit(0);
                    }
                }
            }
        }
    
        public HashTable(int size) {
            this.size = size;
            empLinkedList = new EmpLinkedList[size];
            for (int i = 0; i < size; i++) {
                empLinkedList[i] = new EmpLinkedList();
            }
        }
    
        public void add(Emp emp) {
            int hash = getHash(emp.id);
            empLinkedList[hash].add(emp);
        }
    
        public Emp findEmyById(int id) {
            return empLinkedList[getHash(id)].findById(id);
        }
    
        public void removeById(int id) {
            empLinkedList[getHash(id)].removeById(id);
            System.out.println("删除成功,id为:" + id);
        }
    
        public void update(Emp emp) {
            empLinkedList[getHash(emp.id)].update(emp);
        }
    
        public void list() {
            for (int i = 0; i < size; i++) {
                empLinkedList[i].list();
            }
        }
    
        public int getHash(int id) {
            return id % size;
        }
    }
    
    class Emp {
        public int id;
        public String name;
        public Emp next;
    
        public Emp(int id, String name) {
            this.id = id;
            this.name = name;
        }
    }
    
    class EmpLinkedList {
    
        private Emp head;
    
        // 头结点就是第一个节点
        public void add(Emp emp) {
            if (head == null) {
                head = emp;
                return;
            }
            Emp temp = head;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = emp;
        }
    
        public Emp findById(int id) {
            Emp temp = head;
            if (temp == null) {
                System.out.println("链表为空");
                return null;
            }
            while (true) {
                if (temp.id == id) {
                    return temp;
                }
                if (temp.next == null) {
                    break;
                }
                temp = temp.next;
            }
            return null;
        }
    
        public void update(Emp emp) {
            Emp temp = head;
            if (emp == null || temp == null) {
                return;
            }
            while (true) {
                if (temp.id == emp.id) {
                    temp.name = emp.name;
                    break;
                }
                if (temp.next == null) {
                    break;
                }
                temp = temp.next;
            }
        }
    
        public void removeById(int id) {
    
            Emp temp = head;
            if (temp == null) {
                return;
            }
            while (temp.next != null) {
                if (temp.next.id == id) {
                    temp.next = temp.next.next;
                }
                temp = temp.next;
            }
        }
    
        public void list() {
            Emp temp = head;
            if (temp == null) {
                return;
            }
            while (true) {
                System.out.println("id=" + temp.id + ",name=" + temp.name);
                if (temp.next == null) {
                    break;
                }
                temp = temp.next;
            }
        }
    }
    
    更多相关内容
  • 可扩展哈希表具有插入和删除方法的可扩展哈希表 java 实现。 处理二进制索引。
  • 哈希表java实现

    千次阅读 2020-06-10 17:36:33
    哈希表一、基本概念二、代码实现 一、基本概念 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的...

    一、基本概念

    散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
    给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数。

    1. 结构
      哈希表的结构可以使用数组+链表实现,也可以使用数组+二叉树来实现,因为前面我们还未接触到树这部分内容,所以这里我们就使用数组+链表来实现。这样一个哈希表的结构如下:
      哈希表数据结构
      我们可以看到,哈希表其实就是一个存放着链表的数组构成的,可以理解为就是一个数组,而这个数组中的元素又是一个链表。
    2. 存储
      下面我们来看看哈希表的存储。
        哈希表是根据关键码值(Key value)而直接进行访问的,通过一个散列函数来将码、键进行映射。简单来说,就是我们提前编写一个规则,即函数y=f(key),在存储或访问时,我们通过k进行计算,得到一个位置来进行存储或访问。
        简单举个例子,现有以下一个哈希表,我们给出一个散列函数y=f(key)=key%5(取模)。
      在这里插入图片描述
      假设我们要进行存储的数据关键码值为(1,张三),那么经过散列函数计算:y=1%5=1,那么这个数据将被存放到数组下标为1的位置:
      在这里插入图片描述
      同样我们再随便存储几个数据(2,李四)(6,王五)(49,小明)
      在这里插入图片描述
      为了举例简单,我们这里的散列函数也比较简单,在实际中,有时我们可能需要为了避免冲突而专门设计一个比较复杂的散列函数。

    二、代码实现

    背景:利用哈希表来存储员工信息(id,name),并可以通过id来查找员工

    1. 首先创建一个员工类
    //表示一个员工
    class Emp {
        public int id;
        public String name;
        public Emp next;//默认为空
    
        public Emp(int id, String name) {
            this.id = id;
            this.name = name;
        }
    }
    
    1. 接下来我们创建哈希表中每个数组中存储的链表结构,包括基本的添加(add)、遍历(list)、查找(findEmpById)
    //创建EmpLinkedList,表示链表
    class EmpLinkedList {
        private Emp head;//头指针,默认为空
    
        //添加员工到链表,假设id是自增长的
        public void add(Emp emp) {
            if (head == null) {//如果是第一个员工
                head = emp;
                return;
            }
            //如果不是第一个员工
            Emp temp = head;
            while (true) {
                if (temp.next == null) {
                    break;
                }
                temp = temp.next;
            }
            temp.next = emp;
        }
    
        //遍历链表
        public void list(int no) {
            if (head == null) {//链表为空
                System.out.println("第" + (no + 1) + "条链表为空!");
                return;
            }
            System.out.print("第" + (no + 1) + "条链表的信息为:");
            Emp temp = head;
            while (true) {
                System.out.printf("=> id=%d name=%s\t",temp.id,temp.name);
                if (temp.next == null) {
                    break;
                }
                temp = temp.next;
            }
            System.out.println();
        }
    
        //根据id查找员工
        public Emp findEmpById(int id) {
            if (head == null) {
                System.out.println("链表空");
                return null;
            }
            Emp temp = head;
            while (true) {
                if (temp.id == id) {//找到员工
                    break;
                }
                if (temp.next == null) {//没有找到员工
                    temp = null;
                    break;
                }
                temp = temp.next;
            }
            return temp;
        }
    
    1. 然后来创建一个哈希表结构
    //创建hashtable管理多条链表
    class HashTable {
        private EmpLinkedList[] empLinkedLists;
        private int size;//表示共有多少条链表
    
        //空参构造器,数组默认初始化为5
        public HashTable() {
            this.size = 5;
            empLinkedLists = new EmpLinkedList[size];
            //分别初始化每一个链表
            for (int i = 0; i < size; i++) {
                empLinkedLists[i] = new EmpLinkedList();
            }
        }
    //带参构造器
        public HashTable(int size) {
            //初始化
            this.size = size;
            empLinkedLists = new EmpLinkedList[size];
            //分别初始化每一个链表
            for (int i = 0; i < size; i++) {
                empLinkedLists[i] = new EmpLinkedList();
            }
        }
    
        //添加员工
        public void add(Emp emp) {
            //根据员工id,得到该员工要插入到哪条链表
            int empLinkedListNum = hashFun(emp.id);
            //将emp添加到对应的链表中
            empLinkedLists[empLinkedListNum].add(emp);
    
        }
    
        //遍历所有链表,遍历哈希表
        public void list() {
            for (int i = 0; i < size; i++) {
                empLinkedLists[i].list(i);
            }
        }
    
        //根据id查找员工
        public void findEmpById(int id) {
            //使用散列函数确定到哪条链表中查找
            int empLinkedListNum = hashFun(id);
            Emp emp = empLinkedLists[empLinkedListNum].findEmpById(id);
            if (emp != null) {//找到了
                System.out.printf("在第%d条链表中找到员工 id=%d\n",(empLinkedListNum+1),id);
            } else {
                System.out.println("未找到该员工");
            }
        }
    
        //编写一个简单的散列函数
        public int hashFun(int id) {
            return id % size;
        }
    }
    
    1. 最后写一个简单的Demo来测试
    public static void main(String[] args) {
            //创建一个哈希表
            HashTable hashTable = new HashTable(5);
    
            String key = "";
            Scanner scanner = new Scanner(System.in);
            while (true) {
                System.out.println("add:添加员工");
                System.out.println("list:显示员工");
                System.out.println("find:查找员工");
                System.out.println("exit:退出系统");
    
                key = scanner.next();
    
                switch (key) {
                    case "add":
                        System.out.print("请输入员工id:");
                        int id = scanner.nextInt();
                        System.out.print("请输入员工name:");
                        String name = scanner.next();
                        Emp emp = new Emp(id, name);
                        hashTable.add(emp);
                        break;
                    case "list":
                        System.out.println("员工信息如下:");
                        hashTable.list();
                        break;
                    case "find":
                        System.out.print("请输入要查找的员工id:");
                        id = scanner.nextInt();
                        hashTable.findEmpById(id);
                        break;
                    case "exit":
                        scanner.close();
                        System.exit(0);
                    default:
                        break;
    
                }
            }
        }
    

    我们按照上面举例的数据进行存储
    在这里插入图片描述
    在这里插入图片描述
    根据id查找员工
    在这里插入图片描述

    展开全文
  • 和弦DHT 分布式哈希表Java实现。 该项目是KTH的ID2212 Java网络编程课程的一部分。 :warning: 笔记该项目仅用于个人/教育用途。 它不是,也可能永远不适合生产使用。建造要进行编译(JDK 7):javac -d bin -...
  • 哈希表(Java实现)

    千次阅读 2022-03-13 11:00:37
    代码实现 package com.xz.hashtab; import java.util.Scanner; /** * @author 许正 * @version 1.0 */ public class HashTabDemo { public static void main(String[] args) { //创建HashTab HashTab ...

    基本介绍

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-yw1YIhJc-1647140417398)(C:\Users\许正\AppData\Roaming\Typora\typora-user-images\image-20220312220108011.png)]

    代码实现

    package com.xz.hashtab;
    
    import java.util.Scanner;
    
    /**
     * @author 许正
     * @version 1.0
     */
    public class HashTabDemo {
        public static void main(String[] args) {
            //创建HashTab
            HashTab hashTab = new HashTab(7);
    
            //写一个简单的菜单
            String key = "";
            Scanner scanner = new Scanner(System.in);
            while (true) {
                System.out.println("add:  添加雇员");
                System.out.println("list: 显示雇员");
                System.out.println("find: 查找雇员");
                System.out.println("exit: 退出系统");
    
                key = scanner.next();
                switch (key) {
                    case "add":
                        System.out.print("输入id:");
                        int id = scanner.nextInt();
                        System.out.print("输入姓名:");
                        String name = scanner.next();
                        Emp emp = new Emp(id, name);
                        hashTab.add(emp);
                        break;
                    case "list":
                        hashTab.list();
                        break;
                    case "find":
                        System.out.print("请输入你想要查找的id:");
                        id = scanner.nextInt();
                        hashTab.findEmpById(id);
                        break;
                    case "exit":
                        scanner.close();
                        System.exit(0);
                    default:
                        break;
                }
            }
        }
    }
    
    class HashTab {
        private EmpLinkedList[] empLinkedLists;
        int size;
    
        public HashTab(int size) {
            this.empLinkedLists = new EmpLinkedList[size];
            for (int i = 0; i < empLinkedLists.length; i++) {
                empLinkedLists[i] = new EmpLinkedList();
            }
            this.size = size;
        }
    
        //添加雇员
        public void add(Emp emp) {
            //根据员工id,得到该员工应该加到哪条链表
            int empLinkedListNo = hashFun(emp.id);
            empLinkedLists[empLinkedListNo].add(emp);
        }
    
        //根据输入的id,查找雇员
        public void findEmpById(int id) {
            //使用散列函数确定到哪条链表查找
            int empLinkedListNO = hashFun(id);
            Emp emp = empLinkedLists[empLinkedListNO].findEmpById(id);
            if (emp != null) {//找到
                System.out.println("在第" + (empLinkedListNO + 1) + "条链表中找到 雇员 id = " + id);
            } else {
                System.out.println("在哈希表中,没有找到该雇员~");
            }
        }
    
    
        //显示所有链表
        public void list() {
            for (int i = 0; i < empLinkedLists.length; i++) {
                empLinkedLists[i].list(i);
            }
        }
    
        //散列函数,取模法
        public int hashFun(int id) {
            return id % size;
        }
    }
    
    class EmpLinkedList {
        Emp head = null;
    
        //添加雇员
        public void add(Emp emp) {
            //如果是第一个雇员
            if (head == null) {
                head = emp;
                return;
            }
            //如果不是第一个,创建一个指针,帮助找到链表最后
            Emp temp = head;
            while (true) {
                if (temp.next == null) {
                    break;
                }
                temp = temp.next;
            }
            temp.next = emp;
        }
    
        //遍历雇员信息
        public void list(int no) {
            if (head == null) {
                System.out.println("第" + (no + 1) + "条链表为空!");
                return;
            }
            System.out.print("第" + (no + 1) + "链表的信息为:");
            Emp temp = head;
            while (true) {
                System.out.print("=> id = " + temp.id + " name = " + temp.name);
                if (temp.next == null) {
                    break;
                }
                temp = temp.next;//指针后移
            }
            System.out.println();
        }
    
        //根据id查找雇员
        //如果查找到,就返回Emp, 如果没有找到,就返回null
        public Emp findEmpById(int id) {
            //判断链表是否为空
            if (head == null) {
                System.out.println("链表为空");
                return null;
            }
            //辅助指针
            Emp curEmp = head;
            while (true) {
                if (curEmp.id == id) {//找到
                    break;//这时curEmp就指向要查找的雇员
                }
                if (curEmp.next == null) {//说明遍历当前链表没有找到该雇员
                    curEmp = null;
                    break;
                }
                curEmp = curEmp.next;
            }
    
            return curEmp;
        }
    }
    
    class Emp {
        public int id;
        public String name;
        public Emp next;//next默认为null
    
        public Emp(int id, String name) {
            this.id = id;
            this.name = name;
        }
    }
    
    展开全文
  • 哈希表Java实现

    千次阅读 2022-02-04 10:31:51
    哈希表Java实现

    🚩哈希表(Java实现)

    📚哈希表定义

    哈希表(hash table,也叫散列表),是根据关键码值(key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫散列函数,存放记录的数组叫散列表

    哈希表可以提供快速的插入和查找工作,哈希表运算的非常快,而且编程实现也比较容易。哈希表是数组和链表结构。

    📗哈希表的内存结构示意图

    在散列表中,不像普通数组,每个格子里存放的是一个单一的数据,而是在每一个格子中存放的是一个链表。如图:
    在这里插入图片描述

    📕哈希表存储示意

    哈希表是根据关键码值(key value)而直接进行访问的数据结构,通过一个散列函数来将码、键进行映射。所以我们需要提前编写一个规则,即函数y = f(key); 在存储和访问时,我们通过k进行计算,得到一个位置来进行存储或访问。

    举个例子,如下一个简单的哈希表,我们给出一个关于取模操作的散列函数 y = f(key) = key % 5

    在这里插入图片描述
    现在我们需要插入员工的信息,以员工的编号作为key值,比如我们先插入 (1,吕布) 员工,经过散列函数计算,1 % 7 = 1,所以我们要将该数据插入到数组下标为1的位置去。
    在这里插入图片描述
    同理,我们也将 (2,王昭君),(3,赵云),(8,貂蝉) 数据插入到哈希表中。
    在这里插入图片描述

    📘代码演示

    📭项目背景

    有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,姓名),当输入该员工的id时,要求可以查到该员工的所有信息。
    要求: 不使用数据库,尽量节省内存,速度越快越好(哈希表)。

    📬员工Emp类

    public class Emp {
        private int id;
        private String name;
        private Emp next;
    
        public Emp(int id, String name) {
            this.id = id;
            this.name = name;
        }
    
        public int getId() {
            return id;
        }
        
    	public String getName() {
            return name;
        }
        
        public Emp getNext() {
            return next;
        }
        
        public void setNext(Emp next) {
            this.next = next;
        }
    }
    

    📪链表结构EmpLinkedList类

    包含add添加员工操作,list显示员工信息操作,findEmpById查找员工操作,deleteEmp删除员工操作。

    public class EmpLinkedList {
        private Emp head;
        
        //添加员工
        public void add(Emp emp) {
            //添加的是第一个员工
            if (head == null) {
                head = emp;
                return;
            }
    
            //添加的不是第一个员工
            Emp curemp = head;
            while (true) {
                if (curemp.getNext() == null) {
                    break;
                }
                curemp = curemp.getNext();
            }
            curemp.setNext(emp);
        }
    
        //遍历链表的雇员信息
        public void list(int no) {
            if (head == null) {
                System.out.println("第" + (no + 1) +"条链表为空");
                return;
            }
    
            Emp curemp = head;
            System.out.print("第" + (no + 1) +"条链表信息为:");
            while (true) {
                System.out.printf("员工id:%d\t 员工姓名:%s\t",curemp.getId(),curemp.getName());
                if (curemp.getNext() == null) {
                    break;
                }
                curemp = curemp.getNext();
            }
            System.out.println();
        }
    
    
        //通过员工编号查找员工
        public Emp findEmpById(int id) {
            if (head == null) {
                System.out.println("链表为null");
                return null;
            }
    
            Emp curemp = head;
            while(true) {
                if (curemp.getId() == id) {
                    return curemp;
                }
                if (curemp.getNext() == null) {
                    curemp = null;
                    break;
                }
                curemp = curemp.getNext();
            }
            return curemp;
        }
    
        //通过员工编号删除员工
        public boolean deleteEmp(int id) {
            if (head == null) {
                return false;
            }
    
            if (head.getNext() == null && head.getId() == id) {
                head = null;
                return true;
            }
    
            Emp curemp = head;
            while(true) {
                if (curemp.getNext().getId() == id) {
                    curemp.setNext(curemp.getNext().getNext());
                    return true;
                }
                if (curemp.getNext().getNext() == null) {
                    break;
                }
            }
            return false;
        }
    }
    
    

    📫HashTab类

    public class HashTab {
        private EmpLinkedList[] empLinkedListArray;
        int size;
    
        public HashTab(int size) {
            this.size = size;
            empLinkedListArray = new EmpLinkedList[size];
            for (int i = 0;i < size;i++) {
                empLinkedListArray[i] = new EmpLinkedList();
            }
        }
    
        //添加雇员
        public void add(Emp emp) {
            int emplinkedListArrayNo = hashFun(emp.getId());
            empLinkedListArray[emplinkedListArrayNo].add(emp);
        }
    
        //遍历所有的链表
        public void list() {
            for (int i = 0; i < size; i++) {
                empLinkedListArray[i].list(i);
            }
        }
    
        //查找
        public void findEmpById(int id) {
            int emplinkedListArrayNo = hashFun(id);
            Emp emp = empLinkedListArray[emplinkedListArrayNo].findEmpById(id);
            if (emp == null) {
                System.out.println("没有找到~~");
            }else {
                System.out.printf("找到了,在第%d条链表中,id = %d",emplinkedListArrayNo + 1,id);
            }
            System.out.println();
        }
    
        //删除员工
        public void deleteEmp(int id) {
            int emplinkedListArrayNo = hashFun(id);
            boolean res = empLinkedListArray[emplinkedListArrayNo].deleteEmp(id);
            if (res) {
                System.out.println("删除成功");
            }else {
                System.out.println("没有此员工");
            }
        }
    
        //散列函数 取模法
        public int hashFun(int id) {
            return id % size;
        }
    }
    
    

    📭哈希表测试类HashTabDemo

    import java.util.Scanner;
    
    public class HashTabDemo {
        public static void main(String[] args) {
            HashTab hashTab = new HashTab(7);
    
            int key = -1;
            Scanner scanner = new Scanner(System.in);
            while (true) {
                System.out.println("--------1.添加雇员-----------");
                System.out.println("--------2.显示雇员-----------");
                System.out.println("--------3.查找雇员-----------");
                System.out.println("--------4.删除雇员-----------");
                System.out.println("--------0.退出系统-----------");
                key = scanner.nextInt();
                switch (key) {
                    case 1:
                        System.out.println("请输入雇员id");
                        int id = scanner.nextInt();
                        System.out.println("请输入雇员姓名");
                        String name = scanner.next();
                        Emp emp = new Emp(id, name);
                        hashTab.add(emp);
                        break;
                    case 2:
                        hashTab.list();
                        break;
                    case 3:
                        System.out.println("请输入要查找的员工编号");
                        id = scanner.nextInt();
                        hashTab.findEmpById(id);
                        break;
                    case 4:
                        System.out.println("请输入要删除的员工编号");
                        id = scanner.nextInt();
                        hashTab.deleteEmp(id);
                        break;
                    case 0:
                        scanner.close();
                        System.exit(0);
                        break;
                }
            }
        }
    }
    
    

    📫结果演示

    在这里插入图片描述

    🃏哈希算法

    🎃哈希算法定义

    由于哈希算法被计算的数据是无限的,而计算后的结果范围有限,因此总会存在不同的数据经过计算后得到的值相同(两个不同的数据计算后的结果一样)。当我们对某个元素进行哈希运算,得到一个存储地址,然后根据地址进行元素的存储操作。

    🎄哈希碰撞定义

    要进行插入的时候,发现已经被其他元素占用了,其实这就是所谓的哈希冲突,也叫哈希碰撞。哈希函数的设计至关重要,好的哈希函数会尽可能地保证计算简单和散列地址分布均匀,但是,我们需要清楚的是,数组是一块连续的固定长度的内存空间,再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢?

    🎋解决哈希碰撞的方式

    🌄线性探测法

    ⛵思想

    主要根据index = val.hashcode()%element.length来解决哈希冲突问题。从数组当前位置(hashcode())开始,找到下一个空位置,进行存放。当数组填充满之后,进行数组的扩容操作,继续存放值。存储的键值对中键相等进行值的覆盖操作。进行扩容后的操作,还得进行元素的重新哈希操作。
    在这里插入图片描述

    🚤代码实现
    import java.util.Arrays;
    import java.util.Map;
    
    //线性探测法
    public class LineHashMap<K extends Comparable<K>, V extends Comparable<K>> {
        private static final double LOAD_FACTOR = 0.75;//扩容因子
        private static final int INIT_CAPACITY = 1 << 4;//默认初始化大小 16
        private Entry<K, V>[] table;
        private int size;//有效个数
    
        public LineHashMap() {
            table = new Entry[INIT_CAPACITY];
            this.size = 0;
        }
    
        public V get(K key) {//有数据 index key 相等 2.有数据 发生冲突 3.没有该数据
            int index = key.hashCode() % table.length;
            //如果发生哈希冲突
            if (table[index].key.compareTo(key) != 0) { //对象比较方式?
                int count = 0;
                int i = index;
                for (; table != null && table[index].key.compareTo(key) != 0; i = ++i % table.length) {
    //                count++;
    //                if (count == table.length) {
    //                    System.out.println("没有该数据");
    //                    return null;
    //                }
                }
                return table[i].value == null ? null : table[i].value;
            }
    
            return table[index].value;
        }
    
        public void rehash() {
            if ((double) size / table.length >= LOAD_FACTOR) {
                Entry<K, V>[] newtable = new Entry[table.length << 1];
    
                for (int i = 0; i < table.length; i++) {
                    int index = table[i].key.hashCode() % newtable.length;
                    if (table[i] != null) {
                        if (newtable[index] == null) {
                            newtable[index] = table[i];
                        } else {
                            int j = index;
                            for (; newtable[j] != null; j = ++j % newtable.length) {
    
                            }
                            newtable[j] = table[i];
                        }
                    }
                }
                table = newtable;
            }
        }
    
        public void put(K key, V value) {
            rehash();
            Entry<K, V> entry = new Entry<>(key, value);
            //需要将entry 放置到下标index = entry.key.hashcode() % table.length
            int index = entry.key.hashCode() % table.length;
            if (table[index] == null) {
                table[index] = entry;
            } else {
                int j = index;
                for (; table[j] != null; j = ++j % table.length) {
    
                }
                table[j] = entry;
            }
            size++;
        }
    
    
        //Entry 静态内部类
        static class Entry<K, V> implements Map.Entry<K, V> {
            private K key;
            private V value;
    
            public Entry(K key, V value) {
                this.key = key;
                this.value = value;
            }
    
            @Override
            public K getKey() {
                return null;
            }
    
            @Override
            public V getValue() {
                return null;
            }
    
            @Override
            public V setValue(V value) {
                return null;
            }
        }
    }
    

    🌅链地址法

    线性探测法当产生哈希冲突的键值对越多,遍历数组的次数就会越多。为了解决这个问题,我们采用数组和链表结合的方式,数组元素是一个链表结构,产生哈希冲突,在相同的索引下标下进行链表的插入操作。

    🏕️思想

    在这里插入图片描述
    不足:

    ① 链地址法存在的不足在于,当产生哈希冲突的节点越多,那么数组索引下标查找就会变成链表的遍历操作。数组的优势在于随机取值,时间复杂度达到O(1),而链表的查找时间效率达到O(n)。
    ② 当产生数组扩容时,所有的元素节点都必须进行重新哈希。

    🏞️代码实现
    import java.util.Map;
    
    public class MyLinkedHashMap<K,V> {
        private static final int INIT_CAPACITY = 1 << 14;
        private static final double LOAD_FACTOR = 0.75;
        private Node<K,V>[] table;
        private int size;//有效个数,数组被占个数
    
        public MyLinkedHashMap() {
            table = new Node[INIT_CAPACITY];
        }
    
    
    
        public void rehash() {
            //扩容
            if ((float)size / table.length >= LOAD_FACTOR) {
                Node<K,V>[] newtable = new Node[table.length << 1];
                size = 0;
                for (int i = 0;i < table.length;i++) {
                    if (table[i] != null) {
                        Node<K,V> p = table[i];
                        for (;p != null; p = p.next) {
    //                        int index = p.n_value.key.hashCode() % newtable.length;
    //                        if (newtable[index] != null) {
    //                            p.next = newtable[index];
    //                            p = newtable[index];
    //                        }else {
    //                            newtable[index] = p;
    //                        }
                            put(p.n_value.key,p.n_value.e_value);
                        }
                    }
                }
                table = newtable;
            }
        }
    
        public void put(K key,V val) {
                rehash();
           Node<K,V> node = new Node<>(key,val,null);
            //扩容?重新哈希
            rehash();
            int index = key.hashCode() % table.length;
            if (table[index] != null) {
                node.next = table[index];
                table[index] = node;
            }else {
                table[index] = node;
            }
            size++;
        }
    
    //    public V get(K key) {
    //        int index = key.hashCode() % hashCode();
    //        if (table[index] == null) {
    //            System.out.println("没有该值");
    //            return null;
    //        }
    //    }
    
        static class Node<K,V> {
            Entry<K,V> n_value;
            Node<K,V> next;
    
            public Node(K key,V value, Node<K, V> next) {
                this.n_value = new Entry<>(key,value);
                this.next = next;
            }
        }
    
        static class Entry<K, V>  { //键值对
            private K key;
            private V e_value;
    
            public Entry(K key, V value) {
                this.key = key;
                this.e_value = value;
            }
        }
    }
    
    展开全文
  • 这个是java版的哈希表演示程序,里面用到的散列函数及处理冲突的方法都相对简单,但是可以加深大家对哈希表的认识。
  • 哈希表的实现(Java实现

    千次阅读 2019-10-26 12:36:06
    哈希表的结构是由数组+链表或者数组+二叉树组成,实现的思路是创建一个固定大小的链表数组,将各条链表交给数组来进行管理,根据自定义的规则,将数据依次插入链表中,这样查找起来会非常方便。 package ...
  • java 实现哈希表

    2021-06-16 16:58:25
    一、哈希表的由来 我们的java程序通过访问数据库来获取数据,但是当我们对数据库所查询的信息进行大量分析后得知,我们要查询的数据满足二八定律,一般数据库的数据基本存储在磁盘当中。这使得每次查询数据将变得...
  • 1、哈希表的基本介绍 哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中的一个...使用链表来实现哈希表,该链表不带头节点 代码实现
  • Java数据结构-哈希表实现(hash)

    千次阅读 多人点赞 2022-03-26 16:10:18
    我想给大家介绍的是哈希表,当我们学集合的时候一定会接触到hashtable,我们却不明白为什么要同时重写equals方法和hashCode方法,今天,我就带大家了解哈希表...哈希表的概述 哈希表的创建思路 哈希表的代码实现与分析 结论
  • Java哈希表及链式哈希表实现

    千次阅读 2019-06-18 14:40:02
    哈希表也称为散列表,是用来存储群体对象的集合类结构。 什么是哈希表 数组和向量都可以存储对象,但对象的存储位置是随机的,也就是说对象本身与其存储位置之间没有必然的联系。当要查找一个对象时,只能以某种...
  • Java简单实现链式哈希表

    千次阅读 2022-02-03 16:08:05
    文章目录什么是哈希表试题代码输出结果 什么是哈希表 散列表(Hash table 也叫哈希表),是通过关键码值(key value)而直接进行访问的数据结构。也就是说,它通过关键码值映射到表中的一个位置来访问记录,以加快...
  • Java哈希表

    2022-04-06 16:41:22
    Java哈希表的介绍与实现
  • 主要介绍了哈希表HashMap的深入学习,哈希表是一种非常重要的数据结构,许多缓存技术(比如memcached)的核心其实就是在内存中维护一张大的哈希表,本文会对java集合框架中HashMap的实现原理进行讲解。感兴趣的话可以...
  • 2.1 数字分析法 写道如果事先知道关键字集合,并且每个关键字的位数比哈希表的地址码位数多时,可以从关键字中选出分布较均匀的若干位,构成哈希地址 2.2 平方取
  • 我的哈希表 使用哈希表创建哈希映射。 用Java编写。 要查看源代码,请输入 src/COP3530 此代码是为 DR 编写的。 MARK WEISS 在 FIU 的数据结构课程。 将本准则用于上述类别可能会带来严重后果。 如果您偶然发现了...
  • JAVA——哈希表

    千次阅读 2022-03-02 18:05:57
    1、HashMap集合底层是哈希表/散列表的数据结构。 2、哈希表是一个怎样的数据结构呢? 哈希表是一个数组和单向链表的结合体。 数组:在查询方面效率很高,随机增删方面效率很低。 单向链表:在随机增删方面效率较...
  • Java哈希表(Hashtable)是如何实现的呢?Hashtable中有一个内部类Entry,用来保存单元数据,我们用来构建哈希表的每一个数据是Entry的一个实例。假设我们保存下面一组数据,第一列作为key, 第二列作为value。
  • 文章目录1、哈希表介绍2、哈希函数H(k)哈希函数的构造方法:(1)直接定址法(2)数字分析法(3)平方取中法(4)折叠法(5)除留余数法(6)随机数法3、解决哈希碰撞1、开放地址法2、链地址法(拉链法)4、实例:...
  • ##Chord 点对点分布式哈希表实现###设计此 Chord DHT 实现包含三个主要组件: 超级节点(SuperNode.java) SuperNode是DHT中的一个众所周知的节点,所有Node和Client在开始运行时都知道它的IP地址,通过RMI连接到...
  • 哈希表和有序表
  • 除留余数法 常用的处理冲突的方法 开放寻址法 再散列法 链地址法(拉链法) 建立一个公共溢出区 二、哈希表的简单实现 散列函数求法:除余留数法 哈希冲突的处理方式:拉链法 图源百度百科 员工类 public class ...
  • Java基础-哈希表

    千次阅读 2020-09-11 15:26:27
    哈希表(Hash table,也叫散列表): 是根据关键码值(Key value)而直接进行访问的数据结构。 也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的...
  • javascript中没有像c#,java那样的哈希表(hashtable)的实现。在js中,object属性的实现就是hash表,因此只要在object上封装点方法,简单的使用obejct管理属性的方法就可以实现简单高效的hashtable。
  • 在本篇文章里小编给大家分享了关于java数据结构和算法中哈希表的相关知识点内容,需要的朋友们学习下。
  • 这是我第一次尝试实现哈希表 . 我正在阅读一些指南,但这似乎不对 . 对于我的所有函数,我必须创建一个新的int然后使用它?对于我所有的函数调用,我正在创建一个“int hi” . 并使用它来散列我正在制作的任何键 . ...
  • 哈希表 1. 哈希表的定义 哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做...
  • Java哈希表及其应用

    2022-02-23 09:46:30
    文章目录哈希表相关定义java哈希表的构造方法 哈希表相关定义 哈希表(hash table):也称散列表,是存储群体对象的集合类结构。是根据**键(Key)**而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个...
  • Java哈希表理解丶代码实现

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 152,457
精华内容 60,982
关键字:

哈希表java实现