数据结构中的数据存储结构有个散列方法

数据结构中的数据存储结构有个散列方法，这种方法是怎么一个方法？最好是能举个形象点的例子。还有就是这种方法有很多优点，能给说说为什么有这些优点

哈希表，优点主要是速度快，不论表中有多少数据，插入删除和查找都只需要接近常量的时间0(1），2. 编程实现相对容易（相对树std::map而言）。

适用场合

1. 如果不需要有序遍历数据，并且可以提前预测数据量的大小，那么哈希表在速度和易用性方面是无与伦比的。
2. 如果需要在一秒种内查找上千条记录通常使用哈希表（例如拼写检查器或者数据库)；哈希表的速度明显比树快，树的操作通常需要O(N)的时间级。

原理

1. 准备大数组用以存储用户数据，数组索引称之为哈希键（hash key）
2. 通过将用户键（user key）转换为哈希键（hash key），并在数组中找寻哈希键对应之数据（bucket）。
3. 通常hash键做取模操作以转换为正确范围之数组索引

简言之就是通过对要搜索的关键字做处理，使之变成"大数组"的下标，访问数据依据下标索引，所以非常的快捷

言归正传，哈希表又名散列表，其主要目的是用于解决数据的快速定位问题。考虑如下一个场景。

一列键值对数据，存储在一个table中，如何通过数据的关键字快速查找相应值呢？不要告诉我一个个拿出来比较key啊，呵呵。

大家都知道，在所有的线性数据结构中，数组的定位速度最快，因为它可通过数组下标直接定位到相应的数组空间，就不需要一个个查找。而哈希表就是利用数组这个能够快速定位数据的结构解决以上的问题的。

具体如何做呢？大家是否有注意到前面说的话：“数组可以通过下标直接定位到相应的空间”，对就是这句，哈希表的做法其实很简单，就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里，而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位。

不知道说到这里，一些不了解的朋友是否大概了解了哈希表的原理，其实就是通过空间换取时间的做法。到这里，可能有的朋友就会问，哈希函数对key进行转换，取余的值一定是唯一的吗？这个当然不能保证，主要是由于hashcode会对数组长度进行取余，因此其结果由于数组长度的限制必然会出现重复，所以就会有“冲突”这一问题，至于解决冲突的办法其实有很多种，比如重复散列的方式，大概就是定位的空间已经存在value且key不同的话就重新进行哈希加一并求模数组元素个数，既 (h(k)+i) mod S , i=1,2,3…… ，直到找到空间为止。还有其他的方式大家如果有兴趣的话可以自己找找资料看看。

本文来自CSDN博客，转载请标明出处： http://blog.csdn.net/zhangdong198677/archive/2008/08/25/2830089.aspx