乘法哈希：h(k) = floor(m(KA mod 1)) 0<A<1
哈希表Python实现 class HashTable: def __init__(self): self.size=11 self.slots=[None]*self.size self.data=[None]*self.size def hash_function(self,key,size): return key%size def rehash(self,old_hash,size): return (old_hash+1)%size def put(self,key,data): hash_value=self.hash_function(key,len(self.slots)) if self.slots[hash_value]==None: self.slots[hash_value]=key self.data[hash_value]=data else: next_slot=self.rehash(hash_value,len(self.slots)) while self.slots[next_slot]!=None and\ self.slots[next_slot]!=key: next_slot=self.rehash(next_slot,len(self.slots)) if self.slots[next_slot]==None: self.slots[next_slot]=key self.data[next_slot]=data else: self.data[next_slot]=data def get(self,key): start_slot=self.hash_function(key,len(self.slots)) data=None stop=False found=False position=start_slot while self.slots[position]!=None and not found and not stop: if self.slots[position]==key: found=True data=self.data[position] else: position=self.rehash(position,len(self.slots)) if position==start_slot: stop=True return data def __getitem__(self,key): return self.get(key) def __setitem__(self,key,data): self.put(key,data) 哈希冲突由于哈希表的大小是有限的，而要存储信息的数量是无限的，因此，对于任何哈希函数，都会出现两个元素映射到同一个位置的情况，这种情况就叫做哈希冲突。
解决哈希冲突的方法：
开放寻址法：如果哈希函数返回的位置已经有值，则可以向后探查新的位置来储存这个值。
线性探查：如果位置p被占用，则探查 p+1,p+2....。
二次探查：如果位置p被占用，则探查p+1**2,p-1**2,p+2**2。
二度哈希：有n个哈希函数，当使用第一个哈希函数h1发生冲突时，则使用h2。
哈希表的快速查找可以以空间换时间，需要保证元素个数除以数组容积小于0.5，这个比值就是装载率。
拉链法：哈希表的每个位置都连接一个链表，当冲突发生时，冲突的元素被加到该位置链表的最后。
拉链表需要保证每一个链表的长度都不要太长。
拉链法的装载率是可以大于一的。
插入、查找等操作的时间复杂度是O(1)的。
哈希在python中的应用字典和集合都是通过哈希表来实现的
集合可以看作没有value的字典，因为集合也有不重复的性质。
通过哈希函数把字典的键映射为函数：
dic = {\'name\':\'cui\'} #可以认为是h(\'name\')=1，则哈希表为[None,\'cui\'] 树形结构 二叉树 二叉树的节点的节点定义在堆排序时曾经介绍了什么是二叉树，当时是用列表来实现的，但是二叉树可能出现空值，浪费空间，所以使用类似链表的存储结构。
class BiTreeNode: def __init__(self,data): self.data=data self.lchild=None self.rchild=Node 二叉树的遍历二叉树的遍历有两类四种：
深度优先：前序遍历，中序遍历，后序遍历。
对于有两个遍历求二叉树的方法：前序找根节点（根在前面），中序找左右子树，后序找根节点（根在后面）
#前序遍历，root为根节点 def pre_order(root): if root: print(root.data,end = \'\') pre_order(root.lchild) pre_order(root.rchild) #中序遍历，如果lchild没值则出栈 def in_order(root): if root: pre_order(root.lchild) print(root.data,end = \'\') pre_order(root.rchild) #后序遍历，如果rchild没值则出栈 def post_order(root): if root: pre_order(root.lchild) pre_order(root.rchild) print(root.data,end = \'\')广度优先：层次遍历
#根据队列实现 def level_order(root): q=deque() q.append(root) while(len(q)>0): x=q.popleft() print(x.data,end=\'\') if x.lchild(): q.append(x.lchild) if x.rchild(): q.append(x.rchild) 二叉搜索树 相关知识点二叉搜索树，也叫二叉排序树，它要求每一个节点左子树的节点都比它小，右子树的节点都比他大。
二叉搜索树的遍历是升序序列
如果y是x左子树的一个节点，那么y.key <=x.key;