• 数据结构---哈希表基本操作浅记

    什么是哈希表？

    哈希表就是借鉴了数组的随机访问能力，利用数组的随机访问的高效性产生了哈希表

    哈希函数其实就是把任意的数据类型转成数组的索引

    e.g. char --> int       char - 'a' = int

            大的int类型转为小的int类型 一般都是取模操作，根据数论摸一个素数

            String --> int           字符串的内部就是字符数组，因此还是按照字符转为int的方式

            其他类型 -- > int      因为任意的数据类型都有toString方法，所以可以先转为String --> int

    什么是哈希冲突？

    不同的两个key值，经过哈希函数的运算得到了两个相同的索引。

    在理论上，数学中的任意函数f(x),两个不相同的x都一定有可能会映射到相同的y，哈希冲突无法避免！

    怎们解决哈希冲突？

    1.闭散列：

    当发生冲突时，找到冲突位置的旁边是否存在空闲位置，直到找到第一个空闲位置放入元素。

    好存难查更难删，工程中很少使用此方案

    图解: 

     

    查找：

    要查找120时，先120 %101 = 19,发现19这个位置存放的不是120，则继续向后找，直到找到120位置，若一直向后遍历走完整个数组还没找到，则这个元素不存在。

    若整个哈希表冲突非常严重，此时查找一个元素从O(1)=>遍历数组O(n)。所以一般不用

    2.开散列：

     

    查找任意元素:

    如果取模后若冲突，遍历链表。 在最坏情况下，开散列方案遍历链表，相较于闭散列方案查找次数会大大降低，元素删除，查找，链表的对应操作，相较于闭散列方案来说容易很多。

    若遇见最最最坏的情况，若当前哈希表中某个位置，比如图中19这个位置冲突非常严重，恰好每个元素取模后都是19，某个数组对应的链表的长度过长，查找效率就会降低。面对这种情况一般有两种解决方案：

    1.针对整个数组进行扩容(比如现在数组长度101，扩容到202)就会由原先%101 => %202，很多原来同一个链表上的元素均分到其他新的位置，降低哈希冲突。 e.g. C++中的STL的Map

    2.将这个冲突严重的链表再次变为新的哈希表/二分搜索树(将O(n) => O(logn))不用整张哈希表进行处理，只处理冲突严重的链表。 e.g. JDK的方案

     第二种方法如图：

     

    练习题：

    已知一个线性表(38，25，74，63，52，48)，假定采用散列函数h (key) = key%7计算散列地址，并散列存储在散列表A[...6]中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为（C）

            A.1.5                                 B.1.7                                 C.2.0                                 D.2.3

     

    解：

    成功查找的平均查找长度为：​当前表中所有元素的查找次数 / 表中有效的元素个数 --> 12/6 =2

     拓展：开散列时：

     

    小结：

    对于一般场景下的哈希函数的设计:

    一般来说不用自己写，用现成的即可。MD5,MD4,MD3 SHA1,SHA256 MD5—般用在字符串计算hash值的特点:

    1.定长。无论输入的数据有多长，得到的MD5值长度固定。

    2.分散。如果输入的数据稍有偏差，得到的MD5值相差很大(冲突概率非常低，工程领域忽略不计)

    3.不可逆。根据字符串计算md5很容易，想通过得到的md5还原字符串到底是啥非常难(基本不可能)

    4.根据相同的数据计算的md5值稳定的，不会发生变化。 稳定性是所有哈希函数都要满足的特点

    MD5用途：

    1.作为hash运算

    ⒉.用于加密

    3.对比文件内容(内容稍有修改，得到的md5值天差地别)。上传下载。

     自己设计一个开散列代码：

    完整代码：

    1. import java.util.NoSuchElementException;
    2.  
    3. /**
    4.  * @Author qiqichongya
    5.  * @Date 2022/8/14 19:20
    6.  * @PackageName:HashMap
    7.  * @ClassName: HashMapTest
    8.  * @Description: 自己设计一个 开散列
    9.  */
    10. public class MyHashMap {
    11.     // 有效节点数
    12.     private int size;
    13.     // 实际存储元素的 Node 数组
    14.     private Node[] hashTable;
    15.     // 取模数
    16.     private int M;
    17.     // 负载因子
    18.     private static final double LOAD_FACTOR = 0.75;
    19.  
    20.  
    21.     public MyHashMap() {
    22.         this(16);
    23.     }
    24.  
    25.     public MyHashMap(int init) {
    26.         this.hashTable = new Node[init];
    27.         this.M = init;
    28.     }
    29.  
    30.     /**
    31.      * 对key求哈希值
    32.      *
    33.      * @param key
    34.      * @return
    35.      */
    36.     public int hash(int key) {
    37.         return Math.abs(key) % M;
    38.     }
    39.  
    40.     /**
    41.      * 将一对
    42.      *
    43.      * @param key
    44.      * @param val
    45.      */
    46.     public int put(int key, int val) {
    47.         // 1.先取模找到key对应的Node数组中的索引下标。
    48.         int index = hash(key);
    49.         // 2.遍历对应索引下标的链表，查询key是否已经存在
    50.         for (Node x = hashTable[index]; x != null; x = x.next) {
    51.             if (x.key == key) {
    52.                 int oldValue = x.value;
    53.                 x.value = val;
    54.                 return oldValue;
    55.             }
    56.         }
    57.         // 此时说明该键值对是一个新的，需要新增节点头插到哈希表中
    58.         // 也就是说 此时 Node x == null --> hashTable[index] == null --> 还没有放值。
    59.         Node node = new Node(key, val);
    60.         node.next = hashTable[index];
    61.         hashTable[index] = node;
    62.         size++;
    63.         if (size >= hashTable.length * LOAD_FACTOR) {
    64.             expansion();
    65.         }
    66.         return val;
    67.     }
    68.  
    69.     /**
    70.      * 数组扩容为原来的二倍 和 搬移数据
    71.      */
    72.     private void expansion() {
    73.         // 1.产生一个新的数组并且长度是原来长度的二倍。
    74.         Node[] newTable = new Node[hashTable.length << 1];
    75.         // 2.进行元素的搬移操作，此时取模应该为新的数组长度
    76.         this.M = newTable.length;
    77.         for (int i = 0; i < hashTable.length; i++) {
    78.             for (Node x = hashTable[i]; x != null; ) {
    79.                 // 求出 x 在新的数组中的索引下标
    80.                 int index = hash(x.key);
    81.                 Node next = x.next;
    82.                 // 在新数组中进行头插
    83.                 x.next = newTable[index];
    84.                 newTable[index] = x;
    85.                 // 继续搬移剩下的链表节点。
    86.                 x = next;
    87.             }
    88.         }
    89.     }
    90.  
    91.     /**
    92.      * 判断key是否存在
    93.      *
    94.      * @param key
    95.      * @return
    96.      */
    97.     public boolean containsKey(int key) {
    98.         int index = hash(key);
    99.         for (Node x = hashTable[index]; x != null; x = x.next) {
    100.             if (x.key == key) {
    101.                 return true;
    102.             }
    103.         }
    104.         return false;
    105.     }
    106.  
    107.     /**
    108.      * 判断value是否存在
    109.      *
    110.      * @param value
    111.      * @return
    112.      */
    113.     public boolean containsValue(int value) {
    114.         // 全表扫描
    115.         for (int i = 0; i < hashTable.length; i++) {
    116.             for (Node x = hashTable[i]; x != null; x = x.next) {
    117.                 if (x.value == value) {
    118.                     return true;
    119.                 }
    120.             }
    121.         }
    122.         return false;
    123.     }
    124.  
    125.     /**
    126.      * 在哈希表删除指定键值对（key,value）
    127.      *
    128.      * @param key
    129.      * @param value
    130.      * @return
    131.      */
    132.     public boolean remove(int key, int value) {
    133.         // 先拿到当前 key 在数组中的索引
    134.         int index = hash(key);
    135.         // 判断头节点是不是待删除节点
    136.         Node head = hashTable[index];
    137.         if (head.key == key && head.value == value) {
    138.             // 此时头节点就是待删除节点
    139.             hashTable[index] = head.next;
    140.             size--;
    141.             return true;
    142.         }
    143.         // 此时头节点不是待删除节点
    144.         Node prev = hashTable[index];
    145.         while (prev.next != null) {
    146.             if (prev.next.key == key && prev.next.value == value) {
    147.                 // 此时当前节点是待删除节点的前驱节点
    148.                 Node current = prev.next;
    149.                 prev.next = current.next;
    150.                 size--;
    151.                 return true;
    152.             } else {
    153.                 prev = prev.next;
    154.             }
    155.         }
    156.         // 哈希表中没有这个节点
    157.         throw new NoSuchElementException("no such node!remove error");
    158.     }
    159. }
    160.  
    161. class Node {
    162.     // 对key进行hash运算
    163.     int key;
    164.     int value;
    165.     // 下一个节点的地址
    166.     Node next;
    167.  
    168.     public Node(int key, int value) {
    169.         this.key = key;
    170.         this.value = value;
    171.     }
    172. }

    查找：

    1.     /**
    2.      * 判断key是否存在
    3.      *
    4.      * @param key
    5.      * @return
    6.      */
    7.     public boolean containsKey(int key) {
    8.         int index = hash(key);
    9.         for (Node x = hashTable[index]; x != null; x = x.next) {
    10.             if (x.key == key) {
    11.                 return true;
    12.             }
    13.         }
    14.         return false;
    15.     }
    16.  
    17.     /**
    18.      * 判断value是否存在
    19.      *
    20.      * @param value
    21.      * @return
    22.      */
    23.     public boolean containsValue(int value) {
    24.         // 全表扫描
    25.         for (int i = 0; i < hashTable.length; i++) {
    26.             for (Node x = hashTable[i]; x != null; x = x.next) {
    27.                 if (x.value == value) {
    28.                     return true;
    29.                 }
    30.             }
    31.         }
    32.         return false;
    33.     }

    哈希表删除指定键值对：

    1.     /**
    2.      * 在哈希表删除指定键值对（key,value）
    3.      *
    4.      * @param key
    5.      * @param value
    6.      * @return
    7.      */
    8.     public boolean remove(int key, int value) {
    9.         // 先拿到当前 key 在数组中的索引
    10.         int index = hash(key);
    11.         // 判断头节点是不是待删除节点
    12.         Node head = hashTable[index];
    13.         if (head.key == key && head.value == value) {
    14.             // 此时头节点就是待删除节点
    15.             hashTable[index] = head.next;
    16.             size--;
    17.             return true;
    18.         }
    19.         // 此时头节点不是待删除节点
    20.         Node prev = hashTable[index];
    21.         while (prev.next != null) {
    22.             if (prev.next.key == key && prev.next.value == value) {
    23.                 // 此时当前节点是待删除节点的前驱节点
    24.                 Node current = prev.next;
    25.                 prev.next = current.next;
    26.                 size--;
    27.                 return true;
    28.             } else {
    29.                 prev = prev.next;
    30.             }
    31.         }
    32.         // 哈希表中没有这个节点
    33.         throw new NoSuchElementException("no such node!remove error");
    34.     }

  • 相关阅读:
    R | R及Rstudio安装、运行环境变量及RStudio配置
    攻防世界题目练习——Web引导模式（一）
    Java线程池的知识
    linux下mysql主从复制
    C语言青蛙爬井（ZZULIOJ1072:青蛙爬井）
    学之思第二天-调通登录功能
    Linux线程控制
    原型和原型链
    【51单片机】LED与独立按键（学习笔记）
    [ECCV‘22] Poseur: Direct Human Pose Regression with Transformers
  • 原文地址：https://blog.csdn.net/weixin_53999801/article/details/126348661