[一篇详解哈希表]数据结构之哈希表(散列表)
✅作者简介:大家好,我是Philosophy7?让我们一起共同进步吧!🏆 📃个人主页:Philosophy7的csdn博客
🔥系列专栏: 👑哲学语录: 承认自己的无知,乃是开启智慧的大门
💖如果觉得博主的文章还不错的话,请点赞👍+收藏⭐️+留言📝支持一下博>主哦🤞
文章目录
-
- 散列表
-
- 简介:
- 为什么需要散列表?
- 哈希函数的实现
- 哈希表的代码
散列表
简介:
散列表又可以叫做哈希表,那什么是散列表呢? 现在就让我们深入研究一下吧
是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,或者叫哈希函数,存放记录的数组叫做散列表
为什么需要散列表?
通过上面的描述,相信大家都比较不理解,现在让我们来举一个例子让大家更好的理解散列表。
相信大家会经常用到某某词典
,而每次去搜索一个单词,如果都去查询数据库,那么将会大大影响到这个查询效率,而如果我们去查找缓存的话那么就会大大的提升了我们查找的效率。
哈希函数的实现
以Java语言为例,这里以常用集合的HashMap,来看一看哈希函数在Java中的实现
我们都知道Java当中以及很多的面向对象语言,每一个对象都有属于自己的HashCode(哈希值),这个哈希值就是用于区分不同对象的重要标识。无论对象自身的类型是什么,哈希值都是一个整数型。所以我们采用取模法实现
索引 = 哈希值 % 数组的长度 = index = HashCode % Array.length
不过JDK(Java Development Kit Java语言的软件开发工具包)中的哈希函数是采用位运算的方式实现,没有直接使用取模法。
通过哈希函数,我们可以把字符串或其他类型的Key,转化成数组的下标
例: 给定一个长度为8的数组 当key = 001121时
index = HashCode(“001121”,“张三”) % Array.length = 1420036703 % 8 = 7
哈希表的代码
哈希表=数组+链表
图解:
package com.philosophy7.hashtable;import java.util.Scanner;public class HashTableDemo { public static void main(String[] args) { //1.创建一个哈希表 HashTable hashTable = new HashTable(7); //菜单 String key = ""; Scanner scanner = new Scanner(System.in); while (true) { System.out.println("1." + "添加员工"); System.out.println("2." + "显示员工"); System.out.println("3." + "查找员工"); System.out.println("0." + "退出系统"); key = scanner.nextLine(); 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); hashTable.add(emp); break; case "2": hashTable.list(); break; case "3": System.out.println("请输入要查找的id"); id = scanner.nextInt(); hashTable.findEmpById(id); break; case "0": scanner.close(); System.exit(0); default: break; } } }}//员工类class Emp{ private int id; private String name; public Emp next; //为了更好的理解指针的操作 在这里我们用public修饰 public Emp(int id, String name) { super(); this.id = id; this.name = name; } public int getId() { return id; } public void setId(int id) { this.id = id; } public String getName() { return name; } public void setName(String name) { this.name = name; } @Override public String toString() { return "Emp{" + "id=" + id + ", name='" + name + '\'' + '}'; }}//创建EmpLinkedList链表class EmpLinkedList{ private Emp head; //头指针 指向的是第一个Emp 因此链表的头 是直接指向第一个Emp //添加员工到列表 id是自增长 //也就是将员工直接添加到链表的尾部 public void add(Emp emp){ //若链表为空 if(head == null){ head = emp; return; } //若链表不为空 -- 创建一个Emp节点(临时节点) 作用:更好的帮助我们进行插入操作 Emp curEmp = head; while (curEmp.next != null){ curEmp = curEmp.next; } //直到不进入循环 就证明该结点 == null 也就是说到了链表的最后一个结点 curEmp.next = emp; //于是将结点信息插入到尾部 } //遍历链表 public void list(int no){ if (head == null){ System.out.println("第" +(no+1)+"条链表空"); return; } //不为空从头部开始遍历 Emp temp = this.head; System.out.print("第" +(no+1) +"条链表信息"); while (temp != null){ System.out.printf("=> id=%d name=%s\t",temp.getId(),temp.getName()); temp = temp.next; //指针往下移 } } //根据id查找雇员 //如果查找到 返回Emp 没有找到返回null public Emp findEmpById(int id){ if (head == null){ System.out.println("链表为空"); return null; } //辅助指针 Emp temp = head; while (true){ if (temp.getId() == id){ //找到 break; //temp指向要查找到的员工 } //退出 遍历到最后一个结点指向为Null 就表示啥也没找到 if (temp.next == null){ System.out.println("在哈希表中,没找到该员工"); temp = null; break; //退出 不退出的话会报空指针异常 } temp = temp.next; //往下找 } return temp; }}//创建哈希表 用于管理多条链表class HashTable{ //数组 用于存放EmpLinkedList链表 private EmpLinkedList[] empLinkedListArray; private int size; //统计链表的条数 public HashTable(int size){ //初始化数组的容量 this.size = size; //1.数组当中存放的是对象 所以默认初始化数据里面都是null 会造成空指针异常 empLinkedListArray = new EmpLinkedList[size]; //仅仅是创建了数组 //2.坑 这个时候需要初始化每条链表 否则将会报空指针异常 for (int i = 0; i < size; i++){ empLinkedListArray[i] = new EmpLinkedList(); } } public void add(Emp emp){ //根据员工的id得到对应的信息,添加到哪条链表 int empLinkedListNo = hashFunction(emp.getId()); //将emp添加到对应的链表中 empLinkedListArray[empLinkedListNo].add(emp); } //遍历所有链表 public void list(){ for (int i = 0; i < size; i++){ empLinkedListArray[i].list(i); } } //哈希函数 --- 采用取模法 当然不是魔法啦 public int hashFunction(int id){ return id % size; } //根据输入的id查找员工 public void findEmpById(int id){ //使用哈希函数确定到哪条链表 int empLinkedNo = hashFunction(id); Emp emp = empLinkedListArray[empLinkedNo].findEmpById(id); if (emp != null){ System.out.println("在第"+(id+1)+"条链表找到了"); }else{ System.out.println("在哈希表没有找到该员工"); } }}