表

表与数组有什么不同呢？

首先我们要明白，他们数据结构不同，定义的运算不同。 表里面的基础现实可以借助数组来实现。
如果是用数据做为存储元素的容器，可以理解表是数组的再一层封装

（单）表的抽象数据结构定义

为了简单起见，我用 ts 的借口来定义了

class Table<T> {
  n:string;
  container:T[]
  function getLen(){}
  function insert(val:T){}
  function del(position:int){}
  function isEmpty(){}
  function getVal(){}
  function  getPosition(){}

}

从定义可以看出，它无非大致 有 插入，删除，判断表是否为空…..,利用表的解决问题的实质，就是操作这些运算，
使表中的元素不断的变化，最后得到结构。

表的实现

主要讲 c 语言的实现 ，有如下方法：

• 数组实现
• 指针实现
• 间接寻找
• 用游标实现：（用数组的下表模拟指针）

前两者，没什么好说的。间接寻址，是 数组元素存的是元素的地址，删除，添加时移动的是元素的地址，相比数组的实现，有利于存储大数据，增加，删除操作时效率不至于低

循环链表

• 单循环
• 双循环

哈希表

首先我们要提一个问题，为何哈希表的结构搜索能达到 o(1)呢？

里面的构造究竟是怎么回事呢？我们来探究一下，

一个 开散列（数组+表）的一个 hash 表如下

[0] [1] [2] [3] [4]
表1 表2  表三 表4 表5

每次加入一个元素的时候，计算一个hash值，也就是 映射到数组的索引,每个表中只有
1～2个元素，这样就能搜索就能达到o(1),空间换时间。
比如: 加入 元素 6, 计算hash 等于 6-2=4 .索引值为4，存到第5个表中。

用于计算 hash 值的函数叫做 hash 函数，只要有一个好点的 hash 函数，映射相应的位置，那么就能到达
o(1)的时间查询。

hash 函数的要求

• 哈希函数应当易于计算，并且尽量使计算出来的索引均匀分布。

hash 值冲突

也可能产生相同的 hash 值，那么如何解决这种冲突呢？

• 线性再探测，index 如果有值 ，查 index+1,然后 index+2
• 拉链法（数组+链表存法）所有冲突的值进入链表。

用途

• hash 表，一般查询，去重。。优化查询

一些概念

负载因子是哈希表的重要参数，其定义为：哈希表中已存有的元素与哈希表长度的比值。

总结

此外简单的一种数据结构，根据其特性，主要运用于数据的检索方面。其 value 的存储依托于数组，原理主要是通过把一个 key(整数，结构体，字符串)传入一个函数（hash 函数）中映射成数组的索引，然后找到其中存储的值。hash 函数 要简单，而计算的 code 值要分布均匀，hash 冲突了怎么办？拉链表以及再探索法