散列结构

散列结构

         散列结构是一种为保证增删效率和查询效效率的数据结构。常见形式是数组+链表。

         散列结构的称呼：散列、哈希、杂凑。 

1.名词解释

         1.散列表/hash表：散列结构中的数组，就是所说的散列表、hash表

         2.hash函数/散列函数：用来计算一个元素应该存放在hash表中的哪个位置，比如取余法（模地址发），对关键信息和hash表的长度进行取余操作，为保证计算出的位置一定在hash表中。

         3.hash碰撞：当两个数据计算出的hash表中的位置相同时，这种现象被称为hash碰撞。

         4.hash桶：为了解决hash碰撞所以产生hash桶，一个hash桶中存储了所有发生hash碰撞的元素，链表就是hash桶的一种实现方式（链地址法，拉链法）

2.散列存储数据的流程

         1.获取关键数据

         2.通过hash函数计算该数据需要存放在hash表中哪个位置

         3.如果没有发生hash碰撞则放在该位置

         4.如果发生了hash碰撞，形成hash桶（链表）    

 3.HashSet在存储数据时的流程

         1.获取关键数据---通过元素的hashCode方法的返回值来获取

         2.通过hash函数计算该数据需要存放在hash表哪个位置

         3.如果没有发生hash碰撞   则放在该位置

         4.如果发生了hash碰撞   形成hash桶（链表）

         形成链表时会触发去重的机制  新来的元素要和链表中的每一个元素进行equals  如果不重复则插在链表末尾（JDK1.8）  而JDK1.7则会插入在链表的最前面

4.HashMap在存储数据时得流程

         1.获取关键数据---通过键的hashCode方法的返回值来获取
         2.通过hash函数 计算该数据需要存放在hash表哪个位置
         3.如果没有发生hash碰撞 则放在该位置
         4.如果发生了hash碰撞 形成hash桶(链表) 
         形成链表时会触发去重得机制 新来的键值对要 使用键和链表中每一个键值对得进行equals 如果重复替换掉重复键值对的值 如果不重复则插在链表末尾（JDK1.8）    JDK1.7则会插入在链表的最前面