知识总览：

拉链法：

开始散列表中没有存储任何数据元素即散列地址上的元素是空的，散列地址可以视为链表的头指针，即没有插入任何元素前链表的头指针是空的。一个散列地址对应一个链表，散列地址上实际没有存数据元素，所有的数据元素都存储在链表上了。

散列表使用拉链法插入元素步骤：

1.根据散列函数算出数据元素要插入的散列地址

2.将新元素插入散列地址对应的链表，可使用头插法(即把元素每次都插入在链表的头部)或尾插法(即把元素每次都插入在链表的尾部)。以下例子默认使用头插法

如开始插入19元素，散列函数计算得出散列地址=6,头插法插在链表头部，后来又插入84数据元素，散列函数计算出的散列地址也是6，头插法则把84插入在链表头部，即84在19上部。。。。。。

散列表使用拉链法查找元素：

 步骤：

1.根据散列函数，计算目标元素的散列地址，找到对应链表

2.顺序查找链表，开始进行关键字比较

如查找目标元素27，由散列函数计算出的散列地址为1，从1对应上的链表从头开始顺序查找，先比较79，不相等继续比较27，相等，关键字比较2次查找成功，即查找长度为2

如查找目标元素66，由散列函数计算出的散列地址为1，从1对应上的链表从头开始顺序查找，先比较79，不相等继续比较27，不相等继续比较1，不相等继续比较14，链表上的元素比较完了也没找到66，则查找失败，关键字比较次数4次，查找长度=4

如查找目标元素21，由散列函数计算出的散列地址为8，8位置上对应的空链表即NULL，则查找失败，因为是空链表NULL没有任何关键字即没有值，所以关键字的比较次数为0次，即查找长度为0，有的教材上也说是1次，在考试中如果么有特别说明就认为是比较0次

散列表使用拉链法删除元素：

 步骤：

1.根据散列函数，计算目标元素的散列地址，找到对应链表

2.顺序查找链表，开始进行关键字比较，在链表中找到目标元素了，再根据链表特性删除

只要能在链表中找到这个元素都能删除。

如下删除目标元素27，由散列函数计算出的散列地址为1，从1对应上的链表从头开始顺序查找，先比较79，不相等继续比较27，相等，关键字查找成功，然后再删除27(跟链表的删除一样)，修改对应的指针

如下删除目标元素20，由散列函数计算出的散列地址为7，从7对应上的链表从头开始顺序查找，先比较20相等，删除20元素，然后把7位置上的链头指针置为空

如下删除目标元素66，由散列函数计算出的散列地址为1，从1对应上的链表从头开始顺序查找，找完了也没找到66，删除失败

 知识回顾：

拓展：

散列表中头插法插入元素时，每次插入的元素都是无序的，导致在散列表查找元素时，只能顺序的在链表一个一个元素挨个比较，效率低，则在链表插入时可以比较元素大小，让链表插入的时候保持一个有序的状态，根据大小把元素插入到链表对应位置，即在插入时也排序，则在查找时效率会高一些

 

又水一篇。。。。。。。。。。以上纯属个人理解。。。。。。。。 。。。。。