数据结构之Map/Set讲解+硬核源码剖析(三)

简介: 数据结构之Map/Set讲解+硬核源码剖析(三)

数据结构之Map/Set讲解+硬核源码剖析(二)+https://developer.aliyun.com/article/1413571

2.其他

当然还有其他方法,这里仅作了解即可

2. 除留余数法--(常用) 设散列表中允许的地址数为m,取一个不大于m,但最接近或者等于m的质数p作为除数,按照哈希函数: Hash(key) = key% p(p<=m),将关键码转换成哈希地址

3. 平方取中法--(了解) 假设关键字为1234,对它平方就是1522756,抽取中间的3位227作为哈希地址; 再比如关键字为4321,对 它平方就是18671041,抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合:不知道关键字的分 布,而位数又不是很大的情况

4. 折叠法--(了解)  折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些),然后将这几部分叠加求和, 并按散列表表长,取后几位作为散列地址。

折叠法适合事先不需要知道关键字的分布,适合关键字位数比较多的情况

5. 随机数法--(了解) 选择一个随机函数,取关键字的随机函数值为它的哈希地址,即H(key) = random(key),其中random为随机数 函数。 通常应用于关键字长度不等时采用此法

6. 数学分析法--(了解) 设有n个d位数,每一位可能有r种不同的符号,这r种不同的符号在各位上出现的频率不一定相同,可能在某 些位上分布比较均匀,每种符号出现的机会均等,在某些位上分布不均匀只有某几种符号经常出现。可根据 散列表的大小,选择其中各种符号分布均匀的若干位作为散列地址。例如: 假设要存储某家公司员工登记表,如果用手机号作为关键字,那么极有可能前7位都是 相同的,那么我们可以 选择后面的四位作为散列地址,如果这样的抽取工作还容易出现 冲突,还可以对抽取出来的数字进行反转(如 1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成12+34=46)等方 法。 数字分析法通常适合处理关键字位数比较大的情况,如果事先知道关键字的分布且关键字的若干位分布较均 匀的情况

 哈希函数设置的越巧妙,越能减少哈希冲突,但无法避免哈希冲突

那如何解决哈希冲突呢?常用的方法有两种:开散列和闭散列

3.哈希冲突的解决

1.闭散列

 也叫开放定址法,当遇到哈希冲突时,如果此时哈希表未满,则证明一定有下标未填充数据,可以将发生哈希冲突的数据填入到空位,所以闭散列的关键是寻找空位,寻找空位有两种方式:线性探测和二次探测

1.线性探测

 所谓的线性探测就是从发生冲突的位置开始,依次向后寻找空位

  • 先利用哈希函数获得元素的插入位置,
  • 如果为空直接插入;不为空,进行线性探测

2.二次探测

 线性探测是从发生冲突的位置依次向后寻找空位,可能会导致数据过于集中,为了避免这种情况,可以采用二次探测来寻找空位

研究表明:当表的长度为质数且表装载因子a不超过0.5时,新的表项一定能够插入,而且任何一个位置都不 会被探查两次。因此只要表中有一半的空位置,就不会存在表满的问题。在搜索时可以不考虑表装满的情 况,但在插入时必须确保表的装载因子a不超过0.5,如果超出必须考虑增容

无论是二次探测还是线性探测,都需要开辟大量的空间来解决哈希冲突,所以通过闭散列的方式来解决哈希冲突会导致空间利用率不高,更合理的解决哈希冲突的方式是开散列,也是Java中JDK的解决方式

2.开散列(重点)

1.概念

 开散列是通过"哈希桶"的方式来解决哈希冲突的,所谓的哈希桶,就是一个特殊的数组,数组的每个元素都是链表

 这样,就算发生了哈希冲突,即产生了相同的下标,不需要再去探测空位置,而是在当前位置插入,形成一个链表,搜索数据时需要先定位到下标,再去遍历下标位置对应的整个链表,知道找到要搜索的数据

注意:

 如果同时满足数组的长度 > 64 && 链表的长度 > 8 此时性能就会下降,可以通过红黑树来提高性能

2.哈希桶的模拟实现
1.当存储的数据是整数(Key的数据类型为Integer)
前期准备:
// 哈希表实际上一个数组  数组的元素是Node
    static class Node {
        public int key;
        public int val;
        public Node next;
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    public Node[] arr;
    public int usedSize;
    public HashBuck() {
        arr = new Node[5];
    }
1.search

 寻找哈希表中是否存在某个元素,存在返回true,不存在返回false;

public boolean search(int key) {
        int index = key % arr.length;
        Node cur = arr[index];
        while (cur != null) {
            if (cur.key == key) {
                return true;
            }
        }
        return false;
    }
2.put

 向哈希表中插入数据  需要先判断是否已经存在要插入的元素  如果存在更新val;不存在,直接插入(哈希表中不能存放两个相同的key)

 同时,随着哈希表中的数据增多,要去判断冲突因子的是否合理,当同时满足数组的长度 > 64 && 链表的长度 > 8时,需要重新更新哈希表的长度,来降低负载因子的大小,降低哈希冲突;更新长度需要重新哈希,因为可能发生数据的移动

// put方法
    public void put(int key,int val) {
        int index = key % arr.length;
        Node cur = arr[index];
        // 遍历整个链表 看是否已经存在相同的key值
        while (cur != null) {
            if (cur.key == key) {
                cur.val = val;
                return;
            }
            cur = cur.next;
        }
        // 头插法  arr[index]其实就是链表的头节点
        Node newNode = new Node(key,val);
        newNode.next = arr[index];
        arr[index] = newNode;
        usedSize++;
        // 判断负载因子此时是否合理
        if(loadFactor() >= 0.75) {
            resize();
        }
    }
    private double loadFactor() {
        return usedSize*1.0 / arr.length;
    }
    private void resize() {
        // 扩大到原来的两倍
        Node[] tmpArr = new Node[arr.length*2];
        // 扩容之后 要进行重新哈希
        for (int i = 0; i <arr.length ; i++) {
            Node cur = arr[i];
            while (cur != null) {
                Node curNext = cur.next;
                int newIndex = cur.key % tmpArr.length;
                // 头插
                cur.next = tmpArr[newIndex];
                tmpArr[newIndex] = cur;
                cur = curNext;
            }
        }
        //数组是对象!!!
        arr = tmpArr;
    }

3.get

 返回关键码Key对应的value  如果不存在返回-1

// get
    public int get(int key) {
        int index = key % arr.length;
        Node cur = arr[index];
        while (cur != null) {
            if(cur.key == key) {
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;
    }
2.数据类型是引用类型
1.前提准备

创建person类

/**
 * 数据类型是引用类型  即Key是引用
 * 建立引用类Person 与 与 id的映射关系
 */
class Person {
    public String id;
    public Person(String id) {
        this.id = id;
    }
    // 存储的对象是一个一个人  key是一个引用类型  想要将类型转化为整数  并比较大小  重写方法
    @Override
    public boolean equals(Object object) {
        if (this == object) return true;
        if (object == null || getClass() != object.getClass()) return false;
        Person person = (Person) object;
        return id == person.id;
    }
    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}
// K,V都是泛型  一定要在类的声明中添加
    static class Node<K,V> {
        public K key;
        public V val;
        public Node<K,V> next;
        public Node(K key, V val) {
            this.key = key;
            this.val = val;
        }
    }
    public Node<K,V>[] arr;
    public int usedSize;
    public HashBuck2() {
        arr = (Node<K, V>[]) new Node[5];
    }
2.put

 对于Person类来说,不能直接让他%length来获取他的下标,只能通过hashCode来获取其hash值,再让hash值取%length,从而获取他的下标

// put在hash中插入数据
    public void put(K key, V val) {
        // 先获取对应的hash值
        int hash = key.hashCode();
        int index = hash % arr.length;
        Node<K,V> cur = arr[index];
        while (cur != null) {
            if(cur.key.equals(key)) {
                cur.val = val;
                return;
            }
            cur = cur.next;
        }
        Node<K,V> newNode = new Node<>(key,val);
        newNode.next = arr[index];
        arr[index] = newNode;
        usedSize++;
        // 判断负载因子此时是否合理
        if(loadFactor() >= 0.75) {
            resize();
        }
    }
    private double loadFactor() {
        return usedSize*1.0 / arr.length;
    }
    private void resize() {
        // 扩大到原来的两倍
        Node<K,V>[] tmpArr = new Node[arr.length*2];
        // 扩容之后 要进行重新哈希
        for (int i = 0; i <arr.length ; i++) {
            Node cur = arr[i];
            while (cur != null) {
               Node curNext = cur.next;
                int newIndex = cur.key.hashCode() % tmpArr.length;
                // 头插
                cur.next = tmpArr[newIndex];
                tmpArr[newIndex] = cur;
                cur = curNext;
            }
        }
        //数组是对象!!!
        arr = tmpArr;
    }
3.get
// get  根据key获得他的val
    public V get(K key) {
        int hash = key.hashCode();
        int index = hash % arr.length;
        Node<K,V> cur = arr[index];
        while(cur != null) {
            if(cur.key.equals(key)) {
                return cur.val;
            }
            cur = cur.next;
        }
        return null;
    }
4.测试
public static void main(String[] args) {
        Person person1 = new Person("123");
        Person person2 = new Person("123");
        HashBuck2<Person,String> hashBuck2 = new HashBuck2<>();
        hashBuck2.put(person1,"lvzi");
        // 输出相同的结果  因为Person中重写了equals和hashcode方法  只要内容相同 就认为他们是相同的且具有相同的hashcode值
        // get方法就是根据hashcode方法得到hashcode
        System.out.println(hashBuck2.get(person1));// 输出lvzi
        System.out.println(hashBuck2.get(person2));// 输出lvzi
    }

注意:

 1.在链表中插入数据时有两种方法,头插或尾插jdk1.8之前采用的是头插,1.8之后采用的是尾插

 2.哈希表的所有方法的时间复杂度都是O(1),获取index,遍历链表,链表的长度一定是常数的,因为有loadFactor的调节,链表长度过长,会使用红黑树来调整

3.对于引用类型来说,要重写equals和hashCode方法;重写equals方法是因为在比较的时候需要通过内容来进行比较;重写hashCode方法,便于利用数字定位类,也便于我们进行存储

4.equals方法和hashCode方法往往是要同时重写的,这是因为在使用哈希表等数据结构时要保证搜索的一致性

  • 如果两个对象通过equals比较返回true,则他们的hashCode值应该相同
  • 如果两个对象通过equals比较返回false,则他们的hashCode值不必须一定不同,但为了检索的效率,一般设置为不同

equals方法和hashCode方法的区别

六.hashMap的一些源码讲解

1.成员变量讲解

// 默认容量是16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    // 最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30;
    // 负载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

以上三个都很好理解,下面看几个较为重要但又陌生的成员变量

// 树化条件  每个链表中的结点>=8
    static final int TREEIFY_THRESHOLD = 8;
    // 解树化条件
    static final int UNTREEIFY_THRESHOLD = 6;
    // 最小的树华条件  哈希表的容量最小是64
    static final int MIN_TREEIFY_CAPACITY = 64;

2.构造方法

public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

为什么哈希表的容量一定要是2的次幂呢?主要有以下两方面原因:

  1. 效率性能方面:在建立映射的过程中,最重要的一步在于获取到要插入数据的下标,在上述的模拟实现中,我们采用的是 hash % arr.length()的方法,但还有另一种更快的方法,就是使用位运算,当哈希表的容量n为2的次幂时 ,hash % n == hash &(n-1),这两种求下标的方式是等价的,使用&运算,可以大大提高运算速度
  2. 哈希函数与桶的关系:使用hash &(n-1)这种方式来获取下标还可以使元素分布更加均匀,降低哈希碰撞的可能性

当n为2的次幂时(4,16,32,64......)时,n-1就是一个每个二进制位都为1的特殊二进制数(15--1111),再通过hash & (n-1)实际上是对hash的每一位都进行了&操作,这种运算等价于hash % n,但是运算效率更高,为什么等价呢?下面附上证明:

 抹除高位,只保留低位就相当于减去高位中所有的2^n的倍数(字丑,见谅)

public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

注意看,这是我们常用的构造方法,但是这里面只设置了负载因子,并没有给容量,但是我们却能够直接使用,这是为什么呢?答案在put方法的源码之中

public V put(K key, V value) {
        // 调用putVal方法
        return putVal(hash(key), key, value, false, true);
    }

目录
相关文章
|
7天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
68 9
|
18天前
|
存储 Java
告别混乱!用Java Map优雅管理你的数据结构
【10月更文挑战第17天】在软件开发中,随着项目复杂度增加,数据结构的组织和管理至关重要。Java中的Map接口提供了一种优雅的解决方案,帮助我们高效、清晰地管理数据。本文通过在线购物平台的案例,展示了Map在商品管理、用户管理和订单管理中的具体应用,有效提升了代码质量和维护性。
62 2
|
18天前
|
存储 Java 开发者
Java Map实战:用HashMap和TreeMap轻松解决复杂数据结构问题!
【10月更文挑战第17天】本文深入探讨了Java中HashMap和TreeMap两种Map类型的特性和应用场景。HashMap基于哈希表实现,支持高效的数据操作且允许键值为null;TreeMap基于红黑树实现,支持自然排序或自定义排序,确保元素有序。文章通过具体示例展示了两者的实战应用,帮助开发者根据实际需求选择合适的数据结构,提高开发效率。
49 2
|
28天前
|
缓存 Java 程序员
Map - LinkedHashSet&Map源码解析
Map - LinkedHashSet&Map源码解析
63 0
|
28天前
|
算法 Java 容器
Map - HashSet & HashMap 源码解析
Map - HashSet & HashMap 源码解析
49 0
|
6天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
45 16
|
6天前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
35 8
|
8天前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
35 4
|
10天前
|
存储 C语言
【数据结构】顺序表(c语言实现)(附源码)
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列,常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构,其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别,并重点介绍了动态顺序表的实现,包括初始化、销毁、打印、增删查改等操作。最后,文章总结了顺序表的时间复杂度和局限性,并预告了后续关于链表的内容。
33 3
|
16天前
|
存储 Java 开发者
Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效
【10月更文挑战第19天】在软件开发中,随着项目复杂度的增加,数据结构的组织和管理变得至关重要。Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效。本文通过在线购物平台的案例,展示了Map在商品管理、用户管理和订单管理中的具体应用,帮助开发者告别混乱,提升代码质量。
24 1

热门文章

最新文章