散列表（1）

散列表概念

键通过散列函数后转换为数组的下标，在对应的下标位置上存储相应的信息

键------>散列函数-------->数组下标------->存储信息

散列函数 

散列函数就是一个函数，能够将给定的key转换为特定散列值。hashValue=hash（key）；

散列函数的要求

1、散列函数计算到的散列值必须是大于等于0的正整数，因为hash值要作为数组的下标

2、if  key1==key2，那么经过hash后得到的哈希值也必相同，hash（key1）==hash（key2）

3、如果键值不同，那么经过hash后得到的哈希值也必不相同（哈希函数的设计目标是减少冲突，但不能保证完全不同的输入总是产生完全不同的哈希值）

散列函数的特点

三里函数计算出的哈希值尽可能的随机并且均匀分布，这样能将散列冲突最小化

散列函数的设计方法

①直接寻址法：

hash（key）=key，也就是说，我们可以取关键字key的某个线性函数为散列地址，即hash（key）=a*key+b；其中a，b为常量

②除留余数法：

对于表厂为m的散列函数，让key和一个指定的数进行取模运算hash（key）=key  mod  p(p<=m)。关键在于选择合适的p，如果p选的不好，可能会容易出现hash冲突。当p取不大于哈希表长的最大质数时，产生的hash函数较好

③平方取中法：

这个方法是先取关键字的平方，然后根据可使用的空间的大小，选取平方数是中间几位为哈希地址hash（key）=key

散列冲突

两个不同发关键字（key），由于散列函数值相同，因而被映射到同一张表位置上，该现象被称为散列冲突

解决方案

开放地址法：

开放地址法的思想是：一旦出现了散列冲突，我们就重新寻址一个空的散列地址

①线性检测：

我们往散列表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，如果后边的都没有，则折回查找，直到找到为止。

②二次检测

二次检测的原理与线性检测的原理一样，只不过线性检测的步长是1，每次每次检测的下标依次是：hash（key）+0，hash（key）+1，hash（key）+2.....，所谓的二次检测指的是每次检测的步长变为原来的二次方，即每次检测的下标为hash（key）+0^2，hash（key）+1^2，hash（key）+2^2.......

③双重散列

使用一组散列函数，hash1（key），hash2（key）.......先用第一个散列函数，计算到的存储位置如果已经被占用，再使用第二个空闲的位置，以此类推，直到找到空闲的存储位置

链表法

在散列表中，数组的每个下标位置我们可以称之为槽或桶，每个槽会对应一条链表，所有散列值相同的元素我们会放到对应的链表中。

基于链表的散列冲突的处理方法比较适合存储大对象，大数据量的的散列表，而且，更灵活，比如用红黑树代替链表

树

1、高度、深度和层

节点的高度：节点到叶子节点的最长路径（边数），所有的叶子节点的高度为0.

节点的深度：根节点的这个节点所经历的变得个数，根的深度为0

节点的层数：节点的深度+1

树的高度：根节点的高度

二叉树

每个节点最多有两个子节点，分别是左子节点和右子节点，不过，二叉树并不要求每个节点都有两个子节点。

满二叉树：叶子节点全都在最底层，除了叶子节点外，每个节点都有左右两个子节点，这种二叉树叫做满二叉树

完全二叉树：叶子节点都在最地下两层，最后一层的叶子节点都靠左排列并且除了最后一层，其他层的节点个树都要达到最大，这种二叉树叫做完全二叉树

树的存储结构

顺序结构：需要开辟一块连续的内存空间存储数据

链式存储：存储空间不连续

链式存储①定义好节点

顺序结构：数组；存储的公式：如果父节点存储i位置，左子节点存储2i位置，右子节点存储2*i+1，i是数组的角标

二叉查找树：若任意节点的右子树不空，则右子树上所有结点的值均大于他的根节点的值，若任意节点的左子树不为空，则左子树上所有节点的值均小于他的根节点的值，

1、定义一个二叉查找树基础数据结构【链表结构】
public class BSTree{
private value;
private Node left;
private Node right;
//初始化构造方法
public Node (Node left,int value,Node right){
this.left=left;
this.value=value;
this.right=right;}}