哈希冲突

哈希冲突

不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

哈希冲突的解决：

1、开放地址法（前提是散列表的长度大于等于所要存放的元素）

发生哈希冲突后，按照某一次序找到下一个空闲的单元，把冲突的元素放入。

2、线性探查法

从发生冲突的单元开始探查，依次查看下一个单元是否为空，如果到了最后一个单元还是空，那么再从表首依次判断。如此执行直到碰到了空闲的单元或者已经探查完所有单元。

3、平方探查法

从发生冲突的单元加上12,22,32,…,n2，直到遇到空闲的单元

4、双散列函数探查法

定义两个散列函数，分别为s1和s2，s1的算法和前面一致，s2取一个1～m-1之间并和m互为素数的数。s2作为步长。

更适合于造表前无法确定表长的情况；平均查找长度较短；适合结点规模较大时。

5、分离链接法：

将哈希值相同的元素构成一个链表，head放在散列表中。一般链表长度超过了8就转为红黑树，长度少于6个就变为链表。缺点：指针需要额外的空间

树

树的遍历

在学习链表和数组这两种线性的数据结构的时候，元素之间的次序是十分容易看出的，毕竟元素的位置就是排着队的，自带次序关系，如果想要遍历整个数据结构，无非就是选择倒着遍历还是正着遍历。

但是在学习二叉树这种半线性结构的时候，也想要遍历整棵树，可是树没有数组、链表这么明显的次序关系，所以需要人为的定义次序关系，即前中后序（VLR，LVR，LRV），这一个过程本质上就是将树的半线性结构转换成线性

结构。

而对于任意一个树节点，选择前中后序中的任意一种，就等于将这个树节点和它的左右孩子的顺序给出。以前只是机械的记忆顺序。

下面举例说明，这是一颗二叉树。由整体思维可以将这个二叉树看成三个大的结点。

即蓝红紫结点，按照我们人为规定的次序，先序，中序，后序整体进行排序

这个时候整体上就将一棵二叉树排好序了。

那么现在需要局部的排序。

局部的排序也需要按照实现人为规定的次序。

由于蓝色结点只有一个元素，所以前中后序都只有他自己一个，就不必排序

所以下面只需要看红色和紫色。

红色子树局部排序

紫色子树局部排序

最后将局部排序结果和相同顺序的整体结果组合。

先序遍历：

中序遍历：