作者前言

大家好,我是阿濠,今篇内容跟大家分享的是数据结构之哈希表,很快乐分享到segmentfault与大家一起学习交换,初次见面请大家多多关照,一起学习提高.

前言介绍

在后面的文章中，先后学习了线性表、数组、字符串和树，并着剖析它们对于数据的增删改查操作对于数据处理他们彼此各有千秋，例如

  • 线性表中的栈和队列对增删有严格要求，它们会更关注数据的程序
  • 数组和字符串须要放弃数据类型的对立，并且在基于索引查找上会更有劣势
  • 树的劣势则体现在数据的档次上

然而它们也存在一些缺点：数据条件的查找，都须要对全副数据或者局部数据进行遍历

有没有一种办法能够省去数据比拟的过程，从而进一步晋升数值条件查找的效率呢？

那么接下来将介绍一种高效率的查找神器：哈希表

一、什么是哈希表？

根本介绍

哈希表名字源于Hash,也能够叫作散列表。哈希表是一种非凡的数据结构，是依据关键码值(Key value)而间接进行拜访的数据结构。它与数组、链表以及树等数据结构相比，有显著的区别。

哈希表的核心思想

在之前的数据结构里，数据的存储地位和数据的具体数值之间不存在任何关系，因而在查找问题时，这些有些数据结构必须采取逐个比拟的办法实现。

而哈希表的设计采纳了函数映射的思维，将记录存储地位和记录关键字关联起来，能够疾速定位到须要查找的记录以及不须要与表中的记录进行比拟后再查找

也就是说，它通过把关键码值映射到表中一个地位来拜访记录，以放慢查找的速度。这个映射函数叫做散列函数，寄存记录的数据叫做散列表。

示例意识哈希表

如果对一个手机通讯录进行存储，并且依据姓名找出一个人的手机，如下所示

  • 张一 ： 13212345678
  • 张二 ： 13112345678
  • 张三 ： 18112345678
  • 张思 ： 18012345678

办法一：定义蕴含姓名、手机号码的构造体、再通过链表把四个联系人的存储起来当要判断'张四'是否在链表中，或者通过'手机号'查找时，须要从链表头结点开始遍历，顺次将节点中的姓名字段与'张四'比拟。

直到查找胜利或者全副遍历一遍为止，这种做法的工夫复杂度为O(n);

办法二：借助哈希表的思路，升高工夫复杂度构建姓名到地址的映射函数，这样能够在O(1)的工夫复杂度实现数据的查找，即"地址 = F(姓名)"

哈希函数

如果对下面的例子采纳的Hash函数为：姓名的每个字的拼音结尾大写字母的ASSII码之和，那么下面的手机通讯录例子如下所示

  • address(张一) = ASCII(Z) + ASCII(Y) = 90 +89 =179
  • address(张二) = ASCII(Z) + ASCII(E) = 90 +69 =159
  • address(张三) = ASCII(Z) + ASCII(S) = 90 +83 =173
  • address(张四) = ASCII(Z) + ASCII(S) = 90 +83 =173

那么就会呈现一个问题：'张三'与'张四'哈希函数值统一，这就造成哈希抵触了！

从实质上来说，哈希抵触只能尽可能的缩小，不能完全避免，因为输出的数据是凋谢汇合

这样就阐明哈希表须要设计正当的哈希函数，并且对抵触有一套解决的机制解决

如何设计哈希函数

对于哈希抵触问题，那么咱们如何设计呢？先来看看罕用的哈希函数办法

一、间接定制法

哈希函数为关键字到地址的线性函数，即 H(key) =a * key + b,这里a 和 b 是常数

二、数字分析法

假如关键字汇合中每个关键字key 都由 s 位数字组成(k1,k2,k3,...,ks)，则从提取散布平均的若干位组成哈希地址

三、平方取中法

如果关键字的每一位都有某些数字反复呈现，并且频率很高，能够先求关键字的平方值，并且通过平方扩充差别，并取两头几位作为最终存储地址

四、折叠法

如果关键字的位数很多，能够将关键字宰割为几个等长的局部，取它们的叠加和的值（舍去进位）作为哈希地址

五、除留余数法

事后设置一个数，对关键字进行取余(%)运算。即地址为 key mod p

如何解决哈希抵触

罕用的哈希函数办法一旦产生哈希抵触，咱们该怎么解决？罕用办法解决介绍

一、线性探测法

当一个关键字和另一个关键字发生冲突时，应用某种探测技术在哈希表中造成一个探测序列，而后沿着探测序列顺次查找上来，一旦碰到一个空的单元时，则插入其中。

顺次插入12，13，25 则无问题，当插入23 时（23 % 11）= 1 造成抵触，地址一 已被占用，因而沿着地址一探测，直至地址四为空，则将插入其中。

二、链地址法

将哈希地址雷同的记录存储在一张线性链表中

哈希表的劣势：

它以提供十分快的 插入 - 删除 - 查找操作 ，无论多少数据，插入和删除只须要靠近常量的工夫，在查找方面，有时候比树还快，根本能够一下定位到查找的元素

哈希表的有余：

哈希表中的数据时没有程序概念的，所以不能以一种固定的形式（比方从小到大）来遍历其中的元素，并且哈希表中key是不容许反复的。

二、通过利用实例意识哈希表

先来看一个理论需要，有一个上机题:

有一个公司,当有新的员工来报道时要求将该员工的信息退出(id、性别、年龄、住址...)

问题：当输出该员工的id时,要求查找到该员工的所有信息.

要求：不应用数据库,尽量节俭内存,速度越快越好,增加时保障id从低到高插入

这个时候就能够应用链表哈希表(Hash table)，解决抵触采纳链地址法

思路图解剖析

哈希表里每个元素都是一个链表，指向雇员信息而雇员信息又能够指向下一个雇员信息，链表治理雇员，而哈希表治理链表.....

//示意雇员类class Emp{    public  int id;     //雇员Id    public String name; //雇员名称    public Emp next;    //下一位雇员       public Emp(int id, String name) {            this.id = id;            this.name = name;    }    }//EmpLinkedList 雇员链表class EmpLinkedList{    //头指针 指向第一个雇员 链表头指针间接指向第一个Emp    private Emp headEmp;    //增加雇员到链表    //1.假如增加雇员时 id是自增长 即id总是从小到大的    // 因而咱们能够假如增加雇员到链表的最初    public void add(Emp emp){        //如果增加的是第一个雇员        if(headEmp == null){            headEmp = emp;            return;        }        //如果不是第一个雇员则应用指针指向帮忙定位到最初        Emp curEmp = headEmp;        while (true){            //阐明已到链表最初了            if (curEmp.next == null){                break;            }            curEmp = curEmp.next;        }        //退出时将以后emp 退出链表        curEmp.next = emp;    }    //依据id 找到对应雇员所在的链表地位    //若没有则返回为空    public Emp findEmpById(int id){        //若链表以后头指针为空则代表链表里没有数据        if(headEmp == null ){            System.out.println("以后链表为空");        }        Emp curEmp = headEmp;        while (true){            //若链表里的id == 要找的id 则代表找到了            if(curEmp.id == id){                break;            }            //链表最初元素也不满足 则链表里没有要找的id            if(curEmp.next ==null){                curEmp = null;                break;            }            //进行后移查找            curEmp = curEmp.next;        }        return curEmp;    }    //遍历以后链表的所有雇员信息    public void list(int no){        //判断以后链表是否有数据        if(headEmp == null){            System.out.println("以后"+(no+1)+"链表为空！");            return;        }        System.out.println("以后"+(no+1)+"链表信息为");        Emp curEmp = headEmp;        while (true){            //输入信息            System.out.printf("=> id=%d name=%s \t ",curEmp.id,curEmp.name);            //如果是最初一个则完结            if (curEmp.next == null){                break;            }            //往后挪动            curEmp=curEmp.next;        }    }}//hasTab 治理多条链表class HashTab{    private EmpLinkedList[] linkedListArray;    private int size;//示意有多少条链表    public HashTab(int size){            this.size = size;                linkedListArray = new EmpLinkedList[size];                //哈希表里的每个链表都初始化创立，否则为链表为空        for (int i =0; i<size; i++){            linkedListArray[i] = new EmpLinkedList();        }    }    //链表增加雇员    public void add(Emp emp){        //依据以后员工的id 找到适合增加的链表        int emplikedListNo = hashFun(emp.id);        linkedListArray[emplikedListNo].add(emp);    }    //遍历linkedListArray里的所有的链表    public void list(){        for (int i = 0 ;i< linkedListArray.length; i++){            linkedListArray[i].list(i);        }    }    //依据输出的id 找到适合的链表进行查找信息    public void findEmpById(int id){        //确定查找的id 在那个链表里        int emplinkedNo = hashFun(id);        Emp emp = linkedListArray[emplinkedNo].findEmpById(id);        if (emp!=null){            System.out.printf("在 %d 该链表中找到该 id = %d 雇员\n ",(emplinkedNo+1),id);        }else {            System.out.println("在哈希表中没有找到输出的id雇员");        }    }    //编写散列函数 应用取模法    public int hashFun(int id){        return id % size;    }}

接下来增加数据测试一下把

public static void main(String[] args) {    //创立长度为 7 的哈希表    HashTab hash =new HashTab(7);    //初始化雇员数据    Emp emp1 =new Emp(1,"张三");    Emp emp2 =new Emp(2,"李四");    Emp emp3 =new Emp(3,"王五");    Emp emp4 =new Emp(8,"王五");    //依据以后雇员id找到适合的链表地位    hash.add(emp1);    hash.add(emp2);    hash.add(emp3);    hash.add(emp4);    //查看以后哈希表里的链表数据    hash.list();    //查找id = 9 的雇员    hash.findEmpById(9);    //查找id = 3 的雇员    hash.findEmpById(3);}输入后果为：以后1链表为空！以后2链表信息为=> id=1 name=张三      => id=8 name=王五      以后3链表信息为=> id=2 name=李四      以后4链表信息为=> id=3 name=王五      以后5链表为空！以后6链表为空！以后7链表为空！在哈希表中没有找到输出的id雇员在 4 该链表中找到该 id = 3 雇员