哈希表的介绍和内存布局

哈希表 : 有称之为: 散列表

哈希表是一种数据结构,而不是一种算法

散列表(Hashtable , 也叫做哈希表) :

是根据关键码值(key - value)而直接进行访问的数据结构,也就是说: 他通过把关键码值映射到表中的一个位置来访问记录,以加快查找速度

• 上面将关键码值映射到表中的一个位置的映射函数我们称之为: 散列函数

• 存放记录(数据)的数组我们就称之为一个散列表(哈希表)

  • 注意: 此时我们说我们的散列表就是一个数组是没有错误的, 我们很多人都是认为我们的哈希表的底层是通过数组加上链表或者是数组加上红黑树来完成的, 这个时候我们的这个理解并没有错, 但是我们其实说哈希表就是一个数组其实也是没有错误的,因为如果我们研究了哈希表的底层结构之后我们就能发现其实我们的哈希表底层是先封装了一个数组,而这个数组中的元素类型是一个链表结点的类型, 所以其实哈希表还是一个数组,只不过这个数组中存放的元素的类型是链表类型而已

    • 所以我们说哈希表是一个数组也没有错,但是我们如果是说哈希表是一个数组加链表或者说是一个数组加红黑树的结构也是没有任何的错误的 —> 因为其实我们的哈希表的底层是将我们的链表或者是红黑树封装到了我们的数组中

    • 我们的数组中就是存放我们的链表的头结点或者是红黑树的根节点

哈希表的内存布局:

我们一般都是使用数组加链表或者是数组加上红黑树来作为哈希表的底层实现结构(这里我们来分析底层使用了数组加上链表的哈希表的底层实现结构)

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MwyUtHqP-1663148179569)(E:\非凡英才\数据结构(java)]\数据结构图解\哈希表的内存布局.png)

哈希表实际使用需求 — Google上机题:

有一个实际需求 : 有一个公式,当有新的员工来报到时,要去将该员工的信息加入(信息有id,年龄, 性别 , 住址…) , 当输入该员工的id的时候要去可以查到该员工的所有信息

题目要求: 不使用数据库, 尽量节省内存 ,速度越快越好

其实上面这个问题真的就是一个实际需求:

假设我们有一个java程序, 我们需要将java程序中的数据存储下来,并会对这些数据进行频繁的查找,我们此时就不适合将这种数据放入到数据库中, 因为这个时候我们要对这些数据进行一个频繁的查找,这个时候如果我们存储到数据库中的话, 那么我们与数据库的交互的次数就会太多, 效率相对来讲比较低 , 并且对于数据库的压力也是比较大的, 所以对于这种问题我们通常都会选择在java程序和数据库之间建立一个缓存层 , 建立了缓存层之后我们的java程序如果要寻找一个数据的时候就会优先到缓存层中去找, 如果数据可以在缓存层中找到,那么此时我们就不需要到数据库中去找了

• 而我们的缓存层的实现方式有两种:
  ①直接使用我们的缓存产品 : Redis , Memcache

  • redis底层数据结构是使用的hash表实现的(这里指的是键值对的数据结构), 而其中的值底层数据结构更是有其余丰富的五种数据结构构成
    1. String类型value底层是简单动态字符串
       • 简单动态字符串其实就有点类似于Java中的StringBuffer和StringBuilder
    2. List类型value底层是快速链表(quickList)
       • 快速链表再底层又是压缩链表(ziplist)
    3. Set类型value底层是字典(dict) [字典是使用hash表实现的, 只不过hash表中所有的value都指向了同一个内部值]
       • 也就是Set就相当于是单列集合
    4. Hash类型value底层是压缩链表(ziplist)和哈希表(hashtable)
    5. ZSet(Sorted Set)类型value底层是哈希表(hashtable)和跳跃表(skiplist)
       • hash表主要是用来关联元素value和权重score, 保证value的唯一性, 而跳跃表主要是用来排序
       • zset中每个元素的value赋予了一个权重score用于排序

  ②自己编写一个缓存(这个缓存我们一般都是使用哈希表来实现的)

  • 因为我们之前并没有像Redis这样的缓存产品,所以我们只能是自己编写缓存层, 我们缓存一般都是使用哈希表来实现的

  • 而我们的哈希表的实现方式一般有两种:
    ①数组 + 链表

    ②数据 + 二叉树

    • 我们使用数组加二叉树创建的哈希表的查找效率更加的高

图解: