数据结构总结---------非线性表（哈希表）

太过爱你忘了你带给我的痛 2022-03-15 10:36 228阅读 0赞

### 数据结构总结---------非线性表（哈希表） ###

*  1.为什么有哈希表？
 *  2.哈希表的结构与特点
 *   *  1.特点
     *  2.结构
     *  3.图解
     *  4.结论
 *  3.哈希表涉及到的概念了解
 *   *  1.hashCode()
     *  2.equals()
     *  3.各种类型数据的哈希码应该如何获取hashCode()值
 *  4.如何避免插入数据时产生冲突？
 *  5.java中的HashSet和HashMap

# 1.为什么有哈希表？ #

**由于前面结构的查询都是通过关键字与给定值比较，来确定位置，效率取决于比较的次数**。而最理想的方法是不需要比较，根据给定值能直接定位记录的存储位置，所以为了解决这个问题我们就需要一种让记录数据存储位置的结构与记录的关键字之间产生一种确定的对应关系，使每个记录的关键字与一个存储位置相对应

# 2.哈希表的结构与特点 #

## 1.特点 ##

块、很快、非常的块

## 2.结构 ##

有很多种，最流行的就是顺序表+链表的结构

## 3.图解 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NjU3OTA5_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NjU3OTA5_size_16_color_FFFFFF_t_70 1]  
**注：主结构是顺序表，然后每个顺序表的节点在单独引出一个链表**

## 4.结论 ##

哈希表查询数据块、删除数据块，更新速度快。但是更新后影响到了哈希码值，就比较繁琐了，比如要删除再添加

# 3.哈希表涉及到的概念了解 #

## 1.hashCode() ##

计算哈希码，是一个整数，根据哈希码可以计算出数据在哈希表中的存储位置

## 2.equals() ##

添加会出现冲突，需要通过equals进行比较，判断是否相同，查询时也需要使用equals进行比较，判断是否相同

## 3.各种类型数据的哈希码应该如何获取hashCode()值 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NjU3OTA5_size_16_color_FFFFFF_t_70 2][]

**注：类的hashcode()是将各个属性的哈希码进行某些相乘运算**

# 4.如何避免插入数据时产生冲突？ #

1.  哈希表的长度和表中的记录数的比例——装填因子：  
    如果Hash表的空间远远大于最后实际存储的记录个数，则容易造成冲突。在实际情况中，一般需要根据最终记录存储个数和关键字的分布特点来确定Hash表的大小。还有一种情况是可能事先不知道最终需要存储的记录个数，则需要动态维护Hash表的容量，此时可能需要重新计算Hash地址  
    装填因子=表中的记录数/哈希表的长度  
    如果装填因子越小，表名表中还有很多空单元，则添加发生冲突的可能性越小；而装填因子越大，则发生冲突的可能性就越大，在查找时所耗费的时间就越多，有相关文献证明当装填因子在0.5左右的时候，Hash的性能能够达到最优，因此，一般情况下，装填因子取经验值0.5
2.  哈希函数的选择  
    直接定址法、平方取中法、折叠法、\*\*除留取余法（y=x%11）\*\*等
3.  处理冲突的方法  
    链地址法 开放地址法 再散列法 建立一个公共溢出区

# 5.java中的HashSet和HashMap #

1.  底层都是使用了哈希表
2.  JDK1.7及之前HashMap就是一个table数组+链表实现的存储结构  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NjU3OTA5_size_16_color_FFFFFF_t_70 3]
3.  JDK1.8发生了一些变化，当链表存储的数据个数大于等于8的时候，不再采用链表存储，而是采用红黑树的存储结构  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NjU3OTA5_size_16_color_FFFFFF_t_70 4]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NjU3OTA5_size_16_color_FFFFFF_t_70]: /images/20220315/3c5a42c0604f404a9f6a3617f6d4b280.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NjU3OTA5_size_16_color_FFFFFF_t_70 1]: /images/20220315/888caadfb11347b499322c947343d08c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NjU3OTA5_size_16_color_FFFFFF_t_70 2]: /images/20220315/77f57ad9812d4844848d9eb20f2660ba.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NjU3OTA5_size_16_color_FFFFFF_t_70 3]: /images/20220315/4f990a7b6f1f40baa5f85d71def4ebc3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NjU3OTA5_size_16_color_FFFFFF_t_70 4]: /images/20220315/ad756a31a0cb404f890310fec8d84316.png