python内置类型有一个字典类型(dict)和两个两个集合类型（set and frozenset）
。在创建空字典和很小字典是，初始分配的存储区可容纳8个元素。
。如果虚妄自定义的对象也能座位dict或者set等的关键码，定义一个hash方法。
hash字典最主要是要解决hash冲突。
hash冲突是肯定存在的，消除冲突的方法分为两类：
-
内消除方法 （基本存储区内部解决冲突问题）
-
外消除方法 （基本存储区外部解决冲突问题）
基本要求
-
保证当前这次存入数据项的工作能
正常完成; -
保证字典的
基本存储性质。
解决冲突的方法
- 开地址法
内消除的基本方法
。在准备插入数据并发现冲突时，设法在基本存储区（顺序表）里为需要插入的数据项另行安排一个位置
.....多种方法，没有全部列出来
探查方法
-
线性探测
缺点：随着表中数据的增加，产生冲突的可能性也不断增长
数据在表中逐渐堆积成段，使线性探查序列变得越来越长
-
双散列探测
位置检查以不同方式跳跃进行，有可能减少关键码堆积的发生。
1、 数据的存储和访问是计算机最基本的功能。
2、数据访问的基本方式基于存储位置。
3、字典的实现可以使用线性结构、树形结构或者其他各种结构。使用：顺序表，二叉树或者其他树形结构。
线性表 连续表 散列表
4、字典分类
静态字典：内容和结构不变，只有检索。
动态字典：动态变化 ，还有插入和删除。
5、平均检索长度 ASL
在一次完整检索过程中比较关键码的平均次数。Average Search Length
6、字典功能
1）作为一种数据结构，支持在字典里存储一批数据项；
2）提供支持数据检索的功能，设法维护从关键码找到相关数据的联系信息。
【1】线性表字典
单链表 ，双链表
。任意排序，插入在表头插入是O(1)操作，检索和删除需要扫描整个表，是O(n)操作
。如果表中的数据项按关键码升序或者降序排列，插入需要检索正确位置，O(n)
删除和检索同需要顺序扫描检查，平均检查半个表，为O(n)操作
。易于实现，结构简单
但是检索效率低，插入、删除的效率也很低
【2】散列表字典 (python采用的散列表技术)
。散列表
。散列表实现字典
1）选定一个整数的下标范围，建立一个包括相应元素位置范围的顺序表
2）映射h h为散列函数，哈希函数 杂凑函数
常用的哈希函数：除余法，基数转换法
网友评论