菜鸟笔记之数据结构（8）

数据结构与算法—哈希表

也叫散列表，是根据关键码值而直接进行访问的数据结构，以加快查找速度。这个映射函数叫做散列函数（哈希函数），存放记录的数组叫做散列表。 散列表是数组+链表实现的。 散列表的结构如下图：

哈希表实现步骤：

存储时，通过哈希函数计算记录的哈希地址，并按此地址存储该记录。查找记录时，同样通过哈希函数计算记录的散列地址，按此散列地址访问该记录。哈希函数可以用除留余数法：添加位置的地址下标 = 关键字 / 数组的大小。

哈希冲突 对不同的关键字可能得到同一散列地址，即k1 ≠ k2，而它们根据哈希函数得到的地址一样，这种现象称为冲突。

解决方法： 开放寻址法 ；再散列法；链地址法；建立一个公共溢出区。

总结：数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。散列表则综合了数组和链表的性能。

---------------------------- 个人学习笔记---------------------------