[一篇详解哈希表]数据结构之哈希表(散列表)

✅作者简介：大家好,我是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

哈希表的代码

哈希表=数组+链表

图解:

packagecom.philosophy7.hashtable;importjava.util.Scanner;publicclassHashTableDemo{publicstaticvoidmain(String[] args){//1.创建一个哈希表HashTable hashTable =newHashTable(7);//菜单String key ="";Scanner scanner =newScanner(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 =newEmp(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;}}}}//员工类classEmp{privateint id;privateString name;publicEmp next;//为了更好的理解指针的操作 在这里我们用public修饰publicEmp(int id,String name){super();this.id = id;this.name = name;}publicintgetId(){return id;}publicvoidsetId(int id){this.id = id;}publicStringgetName(){return name;}publicvoidsetName(String name){this.name = name;}@OverridepublicStringtoString(){return"Emp{"+"id="+ id +", name='"+ name +'\''+'}';}}//创建EmpLinkedList链表classEmpLinkedList{privateEmp head;//头指针 指向的是第一个Emp 因此链表的头 是直接指向第一个Emp//添加员工到列表 id是自增长//也就是将员工直接添加到链表的尾部publicvoidadd(Emp emp){//若链表为空if(head ==null){
            head = emp;return;}//若链表不为空 -- 创建一个Emp节点(临时节点) 作用:更好的帮助我们进行插入操作Emp curEmp = head;while(curEmp.next !=null){
            curEmp = curEmp.next;}//直到不进入循环 就证明该结点 == null 也就是说到了链表的最后一个结点
        curEmp.next = emp;//于是将结点信息插入到尾部}//遍历链表publicvoidlist(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 没有找到返回nullpublicEmpfindEmpById(int id){if(head ==null){System.out.println("链表为空");returnnull;}//辅助指针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;}}//创建哈希表 用于管理多条链表classHashTable{//数组 用于存放EmpLinkedList链表privateEmpLinkedList[] empLinkedListArray;privateint size;//统计链表的条数publicHashTable(int size){//初始化数组的容量this.size = size;//1.数组当中存放的是对象 所以默认初始化数据里面都是null 会造成空指针异常
        empLinkedListArray =newEmpLinkedList[size];//仅仅是创建了数组//2.坑 这个时候需要初始化每条链表 否则将会报空指针异常for(int i =0; i < size; i++){
            empLinkedListArray[i]=newEmpLinkedList();}}publicvoidadd(Emp emp){//根据员工的id得到对应的信息,添加到哪条链表int empLinkedListNo =hashFunction(emp.getId());//将emp添加到对应的链表中
        empLinkedListArray[empLinkedListNo].add(emp);}//遍历所有链表publicvoidlist(){for(int i =0; i < size; i++){
            empLinkedListArray[i].list(i);}}//哈希函数 --- 采用取模法 当然不是魔法啦publicinthashFunction(int id){return id % size;}//根据输入的id查找员工publicvoidfindEmpById(int id){//使用哈希函数确定到哪条链表int  empLinkedNo =hashFunction(id);Emp emp = empLinkedListArray[empLinkedNo].findEmpById(id);if(emp !=null){System.out.println("在第"+(id+1)+"条链表找到了");}else{System.out.println("在哈希表没有找到该员工");}}}