|
阅读：5973回复：0
数据结构---哈希表（散列表）
1.哈希表的概念和思想
哈希表是唯一的专用于集合的数据结构。可以以常量的平均时间实现插入、删除和查找
开始时，给数组的每个元素赋空值，NULL。当要在集合中插入一个关键字为Key的数据元素时，就检查Data[Key]是否为空。如果为空，则吧插入的元素存储在Data[Key]中；如果不为空，则表示遇到重复元素，插入失败。 当要查找某个数据元素时，只需要根据查找的关键字Key直接取出Data[Key]的值，如果Data[Key]的值为空，则表示关键字对应的元素不存在。否则，Data[Key]就是要查找的元素。删除时，只需要将对应数组的元素设为NULL即可。每种操作的时间为一个常量。 散列函数函数的应用带来一个复杂的问题： 因为散列函数的定义域范围比值域大，两个或更多的数据元素可能被映射到同一个位置，称为“冲突或碰撞”。这种情况是不可避免的。因此，实现散列表的两个最基本的问题是：如何设计散列函数，如何解决碰撞。 2.散列函数 在散列表中。插入、删除和查找都会用到散列函数。散列函数的计算速度直接影响散列表的性能。好的散列函数的一个标准就是：计算速度快。另一点就是：结点的散列地址尽可能均匀。使得冲突的机会尽可能少。 常用的散列函数包括直接定址法、保留余数法、数字分析法、平方取中法和折叠法等。 个人理解：最近对散列函数，进行了一个详细了解，hash（哈希）的形式，有点像我们平时所对的键值对的形式，如果我们的数据是使用哈希存储（即键值对）操作，那查找，添加，删除都时间复杂度都为O(1), 非常完美。 但是，有下面几个问题也是需要我们去考虑 1. 每一个数据元素，都对应一个键，我们需要存储这个键值关系，即我们的哈希表（或散列表） 2. 用什么样的方法，给数据元素对应设置不同的键（散列函数的工作），特别是数据较多时，如何让生成的键不重复（即冲突），这是我们要考虑的一个重点。 而上述的散列函数的种类，就是采用不同的算法来生成我们的对应关系。 ps: 以上是我个人的一个理解，用于帮助自己的理解，如有不一样的，欢迎讨论 各种方法的详解参考 ： https://www.cnblogs.com/zhuweiheng/p/8207255.html |
||
最新喜欢： Yoon_m...
|
公众号
