文档章节

Java实现哈希表

盒饭加鸡腿
 盒饭加鸡腿
发布于 09/21 15:41
字数 2500
阅读 13
收藏 0

Java实现哈希表

基本概念

哈希表:Hash Table,也称为散列表。在待存放的数据中定义一个关键字k,通过一个映射关系f,将k映射到一个地址中,这个地址称为散列地址。之后查找该记录时,不用再通过数据对比来查找,而直接使用这条记录的关键字k映射获取数据存放地址,取出该地址数据即可。通过这种方式来存放数据的地址集称为哈希表(散列表)。哈希表下维护了一个数组,数组的索引就是我们要映射得到的地址。

散列函数:将数据的关键字k映射为地址的对应关系f称为散列函数。

冲突:不同的关键字通过同一散列函数f映射的结果相同,即f(k1)=f(k2),这种现象称为冲突,k1和k2称作同义词。

负载因子:负载因子=表中现有数据个数/数组总容量,哈希表维护的是数组,因此我们需要在适当的时候对表进行扩容,这个负载因子就是衡量是否需要扩容,也就是说,当我们规定负载因子为0.75,那么我们每次插入数据时,都可计算负载因子是否大于0.75,若大于,则进行扩容。

设计散列函数

1. 直接寻址法

例如:我们要往哈希表中存放员工的信息,我们就可以直接用员工的年龄来作为散列地址,即f(key)=key;或者我们知道员工的出生年份1980,我们可以用2019-1980作为散列地址,即f(key)=2019-key。也就是说,我们可以取关键字的某个线性函数值为散列地址:f(key)=a · key+b,其中a和b为常数。

2. 数字分析法

例如:我们要往哈希表中存放员工的信息,我们发现员工号的后几位是不重复的,我们就可以用员工号的后几位作为散列地址,员工号为关键字。这种通过分析关键字的某个部分作为散列地址的方法称为数字分析法。

3. 平方取中法

当无法确定关键字中哪几位分布较均匀时,可以先求出关键字的平方值,然后按需要取平方值的中间几位作为哈希地址。这是因为:平方后中间几位和关键字中每一位都相关,故不同关键字会以较高的概率产生不同的哈希地址。例如:我们将员工出生日期作为关键字,19800315,但我们不知道这个出生日期中哪部分分步比较均匀,则可对其平方,得364058420499225‬,再取中间的几位作为散列地址。

4. 折叠法

例如:我们要往哈希表中存放员工的信息,现取员工出生日期作为关键字19800315,我们可以运算19+80+03+15作为散列地址。

5. 随机数法

选择一随机函数,取关键字的随机值作为散列地址,通常用于关键字长度不同的场合。

6. 除留余数法   例如:我们将员工编号20154511作为关键字,虽然这个关键字在所有员工中唯一,但数字过大,因此我们可以对其取模20154511%17=8,我们将结果8作为散列地址,即:f(key)=key MOD p。除留余数法可以在取模之前,先使用上面的1~5种方法,最后将结果取模。

冲突处理

1. 开放寻址法

散列函数Hi=(H(key) + di) MOD m,i=1,2,…,k(k<=m-1),其中H(key)为散列函数,m为散列表长,di为增量序列。若使用H(key)获取的散列地址出现冲突,则可以使用下列三种处理冲突方式:

线性探测:di=1,2,3,…,m-1,即在获得的散列地址后增加步长继续探测是否冲突。

平方探测:di=1^2,-1^2,2^2,-2^2,3^2,…,±(k)^2,(k<=m/2),即在获得的散列地址前后以一定步长继续探测是否冲突。

双散列探测:di=H2(key),2H2(key),3H2(key),…,kH2(key),H2(key)!=0,其中H2(key)为另一个散列函数,我们可以使H2(key)=m - (key MOD m),m为散列表长。

2. 再散列法

H(key)=H3(H2(H(key))) MOD m,其中Hi(key)为散列函数,m为散列表长。即在通过一个散列函数取得的散列地址冲突时,再次通过另一个散列函数计算,直到冲突不再发生为止。

3. 链地址法(拉链法)

在哈希表维护的数组中,每个地址存放的不再是数据,则是一个链表,当冲突发生时,直接将数据放入冲突地址所在的链表中即可。

4. 建立一个公共溢出区

除了建立哈希表必须维护的数组外,在开辟一个数组,专门用来存放发生冲突的数据。

哈希表的优化

优化哈希表,主要是对散列函数的优化和冲突结果的方式优化,来达到用一个关键字更快的访问到对应的数据。

  • 散列函数计算的散列地址越均匀,则更不易发生冲突。例如,若我们使用员工的年龄来直接寻址,0~20岁的员工和60以上的员工较少,大部分的数据都聚集在了21~59之间,这样的散列函数极大地可能会发生冲突,影响寻址时间。
  • 在使用除留余数法时,我们使用H(key) MOD p,p的选取非常关键,p选择的好的话,能够最大程度地减少冲突,p一般取不大于数组大小的最大质数(素数)。
  • 在使用链地址法(拉链法)来处理冲突时,若散列函数计算的散列地址不均匀,则会导致某些链表过长,我们知道链表的查询速度是很慢的,只能逐个比较查询,因此要优先优化散列函数,其次,就算散列函数计算的散列地址分布很均匀,当数据很多时,链表还是会过长,这时我们就可以将链表转化为树去维护,这也是HashMap的做法,当链表长度达到8时,会将链表转为红黑树,当树的节点小于6时,又会转为链表。
  • 无论散列函数计算的散列地址多均匀,当数组的长度固定,但哈希表中的数据越来越多时,冲突的几率会越来越大,解决冲突会影响效率,并且在使用链地址法(拉链法)时,会导致同一链表过长。因此,需要使用负载因子,及时的对数组扩容。

开放寻址法实现简单哈希表

开放寻址法

public class HashTable1 {
    private final int DEFAULT_TABLE_SIZE = 23;  //默认数组大小,这里不做扩容处理
    private int size;   //表中的数据个数
    private Employee[] array = null;    //存放数据的数组

    /**
     * 构造器
     */
    public HashTable1(){
        this.size = 0;
        this.array = new Employee[DEFAULT_TABLE_SIZE];
    }

    /**
     * 散列函数,直接用id做key,取模
     * @param key 员工id
     * @return
     */
    private int hash(int key){
        int address = key%DEFAULT_TABLE_SIZE;
        return address;
    }

    /**
     * 插入数据
     * @param employee
     */
    public void put(Employee employee){
        int address = hash(employee.geteId());  //获取散列地址
        if(array[address]!=null){   //若散列地址的数据不为空,则说明出现冲突,这里使用线性探测处理
            int stepSize =1;
            while (array[address]!=null){
                address = (address+stepSize)%DEFAULT_TABLE_SIZE;
            }
        }
        array[address] = employee;
        this.size++;
        System.out.println("key为"+employee.geteId()+"的数据放入的地址为"+address);
    }

    /**
     * 获取key对应的数据
     * @param key 员工id
     * @return
     */
    public Employee get(int key){
        int address = hash(key);    //获取散列地址
        if(array[address]==null){   //若对应的数据为空,说明没有该数据,返回空
            return null;
        }
        if(array[address].geteId()!=key){   //如果当前散列地址的数据不是要找的数据,则探测要查找的数据
            int stepSize =1;
            while (array[address].geteId()!=key){
                address = (address+stepSize)%DEFAULT_TABLE_SIZE;
            }
        }
        return array[address];
    }
    @Override
    public String toString() {
        if(this.size==0){
            return "哈希表为空";
        }
        String str = "";
        for(int i = 0;i<this.DEFAULT_TABLE_SIZE;i++){
            if(array[i]!=null){
                str += array[i].toString()+"\n";
            }
        }
        return str;
    }

    public int getSize(){
        return this.size;
    }
}

链地址法实现简单哈希表

链地址法

public class HashTable2 {
    private final int DEFAULT_TABLE_SIZE = 23;  //默认数组大小,这里不做扩容处理
    private int size;   //表中的数据个数
    private Node[] array = null;    //存放数据的数组

    /**
     * 构造器
     */
    public HashTable2(){
        this.size = 0;
        this.array = new Node[DEFAULT_TABLE_SIZE];
        for (int i = 0;i<DEFAULT_TABLE_SIZE;i++){   //初始化每个地址的头结点
            array[i] = new Node();
        }
    }

    /**
     * 散列函数,直接用id做key,取模
     * @param key 员工id
     * @return
     */
    private int hash(int key){
        int address = key%DEFAULT_TABLE_SIZE;
        return address;
    }

    /**
     * 插入数据
     * @param employee
     */
    public void put(Employee employee){
        Node node = new Node(); //创建节点,保存数据
        node.data = employee;
        int address = hash(employee.geteId());  //获取散列地址
        Node temp = array[address]; //辅助节点,指向该地址所在链表的最后一个节点
        while (temp.next!=null){
            temp = temp.next;
        }
        temp.next = node;   //加入新节点
        this.size++;    //数据个数增加
    }

    /**
     * 获取key对应的数据
     * @param key 员工id
     * @return
     */
    public Employee get(int key){
        int address = hash(key);    //获取散列地址
        Node temp = array[address].next;    //辅助节点搜索该地址所在链表,查询key
        while (temp!=null&&temp.data.geteId()!=key){
            temp = temp.next;
        }
        if(temp==null){ //如果没有查询到数据,返回空
            return null;
        }
        return temp.data;
    }

    @Override
    public String toString() {
        if(this.size==0){
            return "哈希表为空";
        }
        String str = "";
        for (int i = 0;i<DEFAULT_TABLE_SIZE;i++){
            str += "地址"+i+":"+"\n";
            Node temp = array[i].next;
            while (temp!=null){
                str += "\t"+temp.data.toString()+"\n";
                temp = temp.next;
            }
        }
        return str;
    }

    public int getSize(){
        return this.size;
    }

    class Node{
        Employee data;
        Node next;
    }
}

源码:GitHub

© 著作权归作者所有

盒饭加鸡腿
粉丝 1
博文 11
码字总数 26345
作品 0
宝鸡
私信 提问
可视化的数据结构和算法

还记得之前发布过的那个关于可视化排序的文章吗?在网上又看到了一个旧金山大学David Galles做的各种可视化的数据结构和基本算法的主页,网址在这里,大家可以看看。我把这个页面的目录列在下...

戴威
2011/05/12
1K
5
Java Hashtable 涉及的数据结构、实现及冲突处理

Hashtable 提供的功能 Hashtable是一个线程安全的Map,其线程安全是通过在各个方法上加上synchronized关键字实现的,即:该类只能被一个线程所使用,其他调用该类时会阻塞等待; 实现了哈希表...

666B
2018/11/28
11
0
深入谈谈String.intern()在JVM的实现

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/wangyangzhizhou/article/details/79860622 前言 String 类的方法可能大家比较少用也比较陌生,虽然实际项目中...

超人汪小建(seaboat)
2018/04/09
0
0
Java数据结构知多少?java入门学习

  初学java时,我们会了解到Java工具包提供了强大的数据结构,那么Java的数据结构都有哪几种呢?   一、枚举(Enumeration)接口虽然它本身不属于数据结构,但它在其他数据结构的范畴里应用很...

老男孩Linux培训
2018/07/09
6
1
Java拾遗:002 - HashMap源码解读

哈希表 散列表(Hash Table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。这种数据结构在不考虑哈希碰撞的条件下,有前着O(1)的时间复杂度,所以效率非常高。Java中H...

一别丶经年
2018/08/03
13
0

没有更多内容

加载失败,请刷新页面

加载更多

总结:TCP/IP协议

一、介绍 TCP协议属于OSI七层模型中的传输层协议,提供处于网络连接中的两台计算机之间的数据 传输。   在传输层有两个性质不同的协议:TCP(Transmission Control Protocol,传输控制协议...

浮躁的码农
18分钟前
2
0
一言不合就删库跑路?万名贡献者和阿里巴巴开源的二三事

9 月 27 日云栖大会,阿里巴巴宣布贾扬清担任开源技术委员会负责人。 有人问:开源是为了什么? 从个人视角看,可以证明自己的专业能力,获得行业认可; 从企业视角看,可以建立技术影响力,...

大涛学弟
29分钟前
4
0
JAVA编程注意事项(性能篇)

1. 尽量在合适的场合使用单例 使用单例可以缩短加载的时间,提高加载的效率,单例主要适用于以下三个方面: 第一,控制资源的使用,通过线程同步来控制资源的并发访问; 第二,控制实例的产生...

你好夜故事
31分钟前
5
0
List 前端 AngularJS JS 对IP排序

数据格式 $scope.dataList=[ {"ip":"192.168.10.10", "port":"8080",...}, { "ip":"192.168.10.12", "port":"8080",... } ,.....] 调用 $scope.ipSortForward($scope.dataList,"ip") 核心代码......

最菜最菜之小菜鸟
31分钟前
4
0
浅析Cassandra LeveledCompactionStrategy

前言 Cassandra是基于LSM架构的分布式数据库。LSM中有一个很重要的过程,就是压缩(Compaction)。默认的压缩策略是SizeTieredCompactionStrategy,今天主要说一下另一种压缩策略LeveledComp...

阿里云官方博客
35分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部