【062+week2】第二周学习

[shimmer236]

构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
哈希函数是用来得到给定key值的在哈希表中的存储位置的。并不是固定的，可以自己根据情况来定，一般常用常见的有直接定制法，除留余数法，平方取中法，折叠法，随机数法，数学分析法。
当向该结构插入元素时，存入根据关键码以此函数计算出的位置，当搜索时，也是先要将给定的关键码用函数转换成存储位置进行查找，将得到位置处的元素进行比较，若关键码相同，则搜索成功。但是通过一个哈希函数得到的位置，一定是会有冲突的，
例如用除留余数法，哈希函数为key/100。在此情况下数字1与数字101得到的存储位置就是相同的，这样就是哈希冲突， 哈希冲突一般有两种解决方式，一种是闭散列，另一种是开散列。
闭散列：当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中还有空位，那就可以把key值存放到了列表的下一个空位。
开散列：首先对关键码集合用哈希函数计算哈希表中的偏移位置，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
创建哈希表（散列表）
哈希查找的操作步骤：⑴用给定的哈希函数构造哈希表⑵根据选择的冲突处理方法解决地址冲突⑶在哈希表的基础上执行哈希查找。
建立哈希表操作步骤： ① 取数据元素的关键字key，计算其哈希 函数值。若该地址对应的存储 空间还没有被占用，则将该元素存入；否则执行step2解决冲突。 ② 根据选择的冲突处理方法，计算关键字 key的下一个存储地址。若下一个存储地 址仍被占用，则继续执行step2，直到找 到能用的存储地址为止。
时间复杂度：几乎是O(1)，取决于产生冲突的多少。