哈希表的理解以及实现思路

      在学习过队列、链表、栈和树等基本的数据结构后，会发现各种结构都有自己的优点和缺点，有的查找快，有的删除快，也有的插入快，但好像就找不到既能查找快，又能删除和插入快的一种结构。在认识了哈希表这种特殊的数据结构后次啊发现原来一种数据结构可以由其他基本的数据结构组合而来，由此吸取各个数据结构的优点，但是事情永远没那么简单，只想要拿到好的东西的情况并不存在的，一旦你得到了查找、插入和删除快的集合体时，你会发现它们的缺点居然经过揉合之后成了一个原本的数据结构所没有的“超级缺点”，而且处理不当的话这个缺点就是系统致命的毒瘤，哈希表就是这样的一种集中了几种数据结构的集合体，虽然它在很多方面都能够满足人们对于速度的追求，但是致命的弱点总是存在的。
      现在介绍哈希表的结构：
      哈希表有两种比较常用的实现结构，一种是使用映射将大量大范围的数据映射到一个小的数据范围内，建立起映射公式，比如最简单的公式可以是取模运算。这个映射公式就是所谓的哈希公式。在映射的时候会发现有的数据经过映射都得到了同一个数据，也就是发生了重叠，这时候要保存重叠的数据就可以使用一种基本的数据结构去处理，根据需要选择，如果想要得到很高速度的插入操作，就可以选择链表来各自存储这些重叠的数据，这种方法就是所谓的挂链法，也有的叫做拉链法。也可以使用探测的方法往存储空间后面查找，（存储空间利用标识来唯一确定是否空间可用）直到找到可以存入数据的空间为止，这种方法叫做开放定址法。目前流行的就这两种方法，其余的实现方法尚为研究。
      哈希表中还有一个重要的参数就是装载因子，其值等于已存数据个数和整个表可以存储的数据个数的比值，n（装载因子）=N（已存数据个数）/M（表的容量）*100%，也许有人会问这个因子是用来干嘛的，我一开始也不知道它是干嘛的，但后来自己想了想才知道，原来是用来衡量整个哈希表冲突率的大小的，可以用它来决定是否扩展旧的哈希表。当然了，这个因子的值要根据具体的问题来确定，并不是说它越大或是越小更好的，只能说在具体的问题上它取什么值最好。
      总的说来哈希表的结构就如此，先映射到小范围数据区间里，然后根据需要将经过映射后重叠的数据再一起存入链表或是其他基本数据结构中，以此来获取插入、查找和删除速度很快的数据结构。哦，差点忘记说它的致命缺点了，其实到这里读者也不难发现它的缺陷了，就是更新旧的哈希表的时候会发现，由于哈希公式的参数已经改变，那么之前存入的数据就必须经过新的参数的哈希公式重新计算后存入新的哈希表里面，这样一来在更新表的时候工作量是巨大的。不过也有很多解决方案来处理这个缺点带来的问题，比如说可以备份原始数据，但是存储成本就提高了，总之总有新问题会出现就是。所以还是得乐观一点，没有什么事物或方法是完美的，只能说尽量采取适合当前具体问题的方法去解决问题就足够了。