【数据结构】哈希表

目录

哈希表

基本思想

基本原理

哈希表工作机制简化描述

关于查找、插入和删除

HashMap

主要成员变量

主要方法

内部实现细节

注意事项

哈希表

哈希表是一种基于哈希函数的数据结构，它通过键值对的形式存储数据，并允许通过键快速查找对应的值。Java中的哈希表主要通过HashMap类来实现，它是java.util包的一部分。

基本思想

使用一个数组(table数组)来存放数据，但每个数组位置(也称为槽位或桶)不仅仅存放一个单独的值，而是可以存放一个数据结构来处理哈希冲突。这个数据结构最常见的是链表，但也可以是其他类型的数据结构，比如红黑树(在Java的HashMap中，当链表长度超过一定阈值时，会转换为红黑树以提高性能)

在接下来的学习中，我们会对这句话有更深的

基本原理

1.哈希函数

·哈希函数将键映射到哈希表中的索引位置(也称为桶或槽)

·理想情况下，哈希函数应尽可能均匀地分布键，以减少哈希冲突

注意：我们这里所说的映射并不是在Java中的反射

映射(Mapping)通常指的是将一种数据类型或对象关联到另一种数据类型或对象的过程。在哈希表中，映射特指将键(Key)通过哈希函数转换成一个索引为止，以便快速访问对应的值(Value)。

这种映射是静态的，即在编译时就已经确定了键和索引之间的对应关系(尽管实际的索引计算是在运行时进行的，但映射规则是编译时确定的)

反射(Reflection)

反射是Java语言的一种特性，它允许程序在运行时动态地获取类的信息、调用类的方法或修改类的属性。反射机制使得程序能够灵活地操作对象和类，而无需在编译时直到具体的类名或方法名。反射主要用于框架开发、动态代理、注解处理等场景

区别

·映射是对象之间的关联，通常用于数据结构之间的映射关系，如哈希表。而反射是对类本身进行操作，如获取类的信息、调用方法等

·映射是静态的，即映射规则在编译时确定。而反射是动态的，即可以在运行时获取和操作类的信息

·映射常用于数据处理和快速访问，而反射用于框架开发和实现灵活的功能

2.哈希冲突

·不同的键可能映射到相同的索引位置，这称为哈希冲突

·Java的HashMap使用链表或红黑树来处理冲突

哈希表工作机制简化描述

1. 哈希函数：当我们想要插入一个元素时，首先使用一个哈希函数来计算该元素的哈希值。哈希函数将元素映射到数组的索引上
2. 冲突处理：由于不同的元素可能会映射到数组的同一个索引(即哈希冲突)，所以需要在每个数组位置存储一个能够处理这种冲突的数据结构。最常见的方法是链表法(也叫拉链法)和开放地址法

·链表法：每个数组位置存储一个链表，链表中的每个节点都存储一个元素。当发生哈希冲突时，新元素被添加到响应索引位置的链表的末尾

·开放地址法：当发生哈希冲突时，寻找数组中的下一个空位置来存储元素。这可以通过线性探测、二次探测或双重散列等方法实现

关于查找、插入和删除

·查找：使用哈希函数计算元素的哈希值，然后访问相应索引位置的链表(或其他数据结构)，遍历链表直到找到目标元素或链表末尾

·插入：同样使用哈希函数找到索引位置，然后将新元素添加到相应索引位置的链表中

·删除：也是先找到索引位置，然后在链表中查找并删除目标元素

所以：哈希表使用一个数组table，每个位置可以存放一个能够处理哈希冲突的数据结构(最常见的是链表，但也可以是其他数据结构)

接下来我们这里通过简单讲解HashMap类，来了解如何使用哈希表及其内部方法

HashMap

主要成员变量

·transient Node<K,V>[] table ：存储哈希表的数组，初始化为null，在第一次使用时懒加载并初始化为指定容量

·transient Set<Map.Entry<K,V>> entrySet：存储键值对的集合

·int size：当前存储的键值对数量

·int modCount：记录HashMap修改次数，用于快速失败机制

·int threshold：阈值，当哈希表中的键值对数量超过此值时，会进行扩容

·float loadFactor：加载因子(负载因子)，用于确定何时扩容，默认为0.75f

主要方法

构造方法

1.HashMap()

2.HashMap(int initialcapacity)

3.HashMap(int initialcapacity,float loadFactor)

插入键值对

·put(K key,V value)：将指定的键值对插入哈希表。如果键已存在，则更新其值

·putlfAbsent(K key,V value)：如果指定的键尚未与某个值关联(或映射为null)，则将其与给定值关联并返回null，否则返回当前值

获取值

·get(Object key)：根据键获取值。如果键不存在，则返回null

·getOrDefault(Object key,V defaultValue)：根据键获取值。如果键不存在，则返回指定的默认值。注意：如果指定的键为null，会抛出NullPointerException异常，因为HashMap不允许null键

·containsKey(Object key)：检查哈希表中是否包含指定的键

·containsValue(Object value)：检查哈希表中是否包含指定的值

删除键值对

·remove(Object key)：根据键删除键值对。如果键存在，则返回其对应的值，否则返回null

遍历

·keySet() ：返回包含所有键的集合

·values() ：返回包含所有值的集合

·entrySet() ：返回包含所有键值对的集合

其他

·size() ：返回哈希表中的键值对数量

·isEmpty() ：检查哈希表是否为空

·clear() ：清空哈希表

代码案例：

public static void main(String[] args) {
        //构建一个哈希表
        Map<String,Integer> hashmap=new HashMap<>();
        
        //插入键值对
        hashmap.put("apple",1);
        hashmap.put("banana",4);
        hashmap.put("orange",0);
        
        //获取值
        int a= hashmap.get("banana");
        System.out.println(a);//4
        System.out.println(hashmap.getOrDefault("orange",10));//0
        System.out.println(hashmap.getOrDefault("hhaa",100));//100
        System.out.println(hashmap.containsKey("apple"));//true
        System.out.println(hashmap.containsValue(100));//false
        System.out.println(hashmap.containsValue(1));//true

        //删除键值对
        hashmap.remove("apple");
        System.out.println(hashmap.containsKey("apple"));//false

        //遍历
        System.out.println(hashmap.keySet());//[banana, orange]
        System.out.println(hashmap.values());//[4, 0]
        System.out.println(hashmap.entrySet());//[banana=4, orange=0]
    }

内部实现细节

1.哈希计算

·HashMap使用key.hashCode方法计算键的哈希值，然后进一步处理以减少高位冲突

·indexFor(int h,int length)方法根据哈希值和数组长度计算索引位置

2.扩容

·当哈希表中的键值对数量超过阈值时，会进行自动扩容

·扩容后的数组容量是原来的两倍

·重新计算每个键的索引位置，并将键值对重新插入新的数组

3.链表转红黑树

·在Java 8中，当单个桶的链表长度超过8时，会转换为红黑树以提高查找效率

·当红黑树的大小 小于等于6时，会退化为链表

注意事项

·线程安全性：HashMap不是线程安全性。在多线程环境中，如果多个线程同时访问和修改HashMap，可能会导致数据不一致的问题。可以使用ConcurrentHashMap来替代

·null值：HashMap允许一个null值和多个null值

·性能：哈希表的性能取决于哈希函数的质量以及哈希表的负载因子和初始容量。选择合适的参数可以提高性能