讲解之前我们先讲一个概念——符号表

符号表的最主要作用就是把一个键和一个值联系起来。

我们会使用符号表这个词来描述一张抽象的表格。我们会将信息（值）存在其中，然后按照指定的键来搜索并获取这些信息。

符号表有时被称为字典。就像是一步字典，键是词，值是释义。

符号表有时又叫索引。数组就是索引结构，键即索引，值即数组中的元素。

所有的实现要遵循以下规则：

　　1.每个键只对应一个值（表中不允许存在重复的键）。

　　2.当用例代码向表中存入的键值对和表中已有的键（及关联值）冲突时，新的值会替代旧的值。

1.无序链表查找

我们把所有的元素用一个无序的链表进行存储起来。每一个节点记录key值，value值以及指向下一个记录的对象。

如图，当我们往链表中插入元素的时候，从表头开始查找，如果找到，则更新value，否则，在表头插入新的节点元素。

无序链表的插入和查找的平均时间复杂度均为O(n)。

2.二分查找

和采用无序链表实现不同，二分查找的思想是在内部维护一个按照key排好序的二维数组，每一次查找的时候，跟中间元素进行比较，如果该元素小，则继续左半部分递归查找，否则继续右半部分递归查找。

采用二分查找只需要最多lgN+1次的比较即可找到对应元素，所以查找效率比较高。

但是对于插入元素来说，每一次插入不存在的元素，需要将该元素放到指定的位置，然后，将他后面的元素依次后移，所以平均时间复杂度O(n)，对于插入来说效率仍然比较低。

3.二叉查找树

查找算法