11.1.1 引子:散列的基本思路

场景:编译时，提交给编译系统的是一个源代码，当编译系统碰到变量名的时候，可能存在两个位置，

一个在变量定义的这样一个位置。

另一个在语句里使用一个变量或引用时判断有无定义、变量类型、语句中是否能使用。

抽象一下，这里，此时涉及变量管理的问题，是对变量以及变量的属性的一个管理。

插入:插入到要管理的变量集合中去。

查找:编译时的语句使用这个变量时要在变量集合中找是否存在。

还有可能删除。

这些涉及一个动态查找的问题。

比如在AVL查找数中，要把一个关键词和跟当前结点的关键词比较。

如果是变量名是字符串，那么就需要一个个字符比较，如果是整数，那么就比较一次大小是否相等即可。

(1)顺序查找:放在数组或列表中，从头到尾一个个找，查找效率低。

(2)二分查找是静态查找，从小到大排好序，但不使用现有动态查找场景。

(3)当把搜索树设计成二叉搜索树或平衡二叉树ALV时，如涉及字符串比较时并不合适。

使用二分法处理，时间复杂度和空间复杂度都不错。

而查找依然不合适，关键在于查找关键词的位置，以及字符串一个个字符的大小比较。

有序-全序-完全有序:二分查找，从小到大排好。

有序-半序:某些关键词之间存在一个秩序(半序，个人理解是抽象来说，把对象进行有组织的一种方式)，比如查找树，任何一个结点都比左子树的结点大，比右子树的结点小，这是一种提高查找效率的方法，尽快的计算出所查关键字的位置。

利用此种规律，能找到另外的方法，直接计算出对象所在的位置，利用散列法。

散列函数:根据对象计算所在位置，对象类型整数、字符串、图片等都可以，把对象计算/映射成比较小的整数，代表此对象将来的位置，但无法预计未来的对象是什么。

冲突解决策略:新来的对象计算出的整数与已存在的整数相同，也就是位置相同，如果散列方法设计的好，不发生冲突或很少发生冲突，那么查找效率是很高的。

====主要目标:查找。工作案例:hashmap。主要工作:计算关键词位置以及解决冲突策略。