黑马程序员技术交流社区
标题: 数据结构问题 [打印本页]
作者: 钟成军 时间: 2014-4-1 12:02
标题: 数据结构问题
数据结构有数组结构，链表结构，二叉树结构，哈希表结构
HashSet，HashMap，Hashtable底层数据结构都是哈希表结构，但对于哈希表结构的概念还是有些模糊，哪位大神可以用通俗的方式给解释一下吗？谢谢
作者: yanzhendong 时间: 2014-4-1 12:09
hash表使用Hash算法，根据元素本身的Hash值，将元素映射到数组中的不同位置，比如，Hash表表使用了（n%100）的Hash算法，当元素的Hash值为102时，就映射到数组的第二个位置，当元素的Hash值为20时就映射到数组的第二十个元素位置上，这样当从Hash表中取元素是，只要根据元素的Hash值，再通过Hash算法，就能确定元素在数组中的位置，
作者: victorsun 时间: 2014-4-1 17:56
具体系统的给您解释一下：
哈希表主要是构造一个映射函数，该函数以数据元素为自变量，函数值即为数据元素在内存中的存储位置。通常把这样的映射函数称为哈希函数h(x)。因此可以说，哈希表是通过哈希函数h(x)来确定数据元素x存放位置h(x)的一种特殊存储结构。
1、哈希表的基本构造方法
构造哈希表的方法是：设要存储的数据元素个数为 n，设置一个长度为m（m≥n）的连续内存单元（即数组），分别以每个数据元素的关键字Ki（0≤i≤n-1）为自变量，以哈希函数h(Ki)值为该数据元素在数组中的下标值存储该数据元素。
把构造哈希表时Ki≠Kj（i≠j）,但h(Ki)=h(Kj)的现象称作哈希冲突。
2、 建立哈希表的关键问题
设计一个好的哈希函数，使得尽量避免哈希冲突，以及哈希冲突发生后，如何解决哈希冲突，就成了建立哈希表的两个关键问题。
哈希冲突主要与三个因素有关：
（1）与装填因子a有关。
（2）与所采用的哈希函数有关。
（3）与解决哈希冲突的哈希冲突函数有关。
3、哈希函数构造方法
设要存放的数据元素有n个，存放数据元素的数组个数为m，哈希函数的设计目标，就是要使通过哈希函数得到的n个数据元素的哈希地址 。
1） 除留余数法
除留余数法是用数据元素的关键字K除以哈希表长度m所得的余数作为哈希地址的方法。除留余数法的哈希函数h(K)为：
h(K) = K mod m
2 ）直接定址法
直接定址法是以数据元素的关键字K本身或关键字加上某个数值常量C作为哈希函数的方法。直接定址法的哈希函数h(K)为：
h(K) = K + C
3 数字分析法
数字分析法是取数据元素关键字中某些取值较均匀的数字位构造哈希函数的方法。它只适合于所有关键字值已知的情况。
4、 哈希冲突解决方法
解决哈希冲突的方法主要有开放定址法和链表法两大类。
作者: ╰つ 时间: 2014-4-1 19:28
哈希表就是把空间分成一片一片的区域，然后通过你存入对象，计算出哈希值，然后直接根据哈希值放入指定的区域中，所以也有了hashSet,是无序的，唯一的，
作者: 黄泉 时间: 2014-4-2 17:20
一、哈希表的概念及作用
一般的线性表，树中，记录在结构中的相对位置是随机的，即和记录的关键字之间不存在确定的关系，因此，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较“的基础上，查找的效率依赖于查找过程中所进行的比较次数。
理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。
哈希表最常见的例子是以学生学号为关键字的成绩表，１号学生的记录位置在第一条，１０号学生的记录位置在第１０条...
如果我们以学生姓名为关键字，如何建立查找表，使得根据姓名可以直接找到相应记录呢？
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
刘丽
刘宏英
吴军
吴小艳
李秋梅
陈伟
...
姓名中各字拼音首字母
ll
lhy
wj
wxy
lqm
cw
...
用所有首字母编号值相加求和
24
46
33
72
42
26
...
最小值可能为3 最大值可能为78 可放75个学生
用上述得到的数值作为对应记录在表中的位置，得到下表：
成绩一
成绩二...
3
...
...
...
24
刘丽
82
95
25
...
26
陈伟
...
...
33
吴军
...
...
42
李秋梅
...
...
46
刘宏英
...
...
72
吴小艳
...
...
78
...
上面这张表即哈希表。
如果将来要查李秋梅的成绩，可以用上述方法求出该记录所在位置：
李秋梅:lqm 12+17+13=42 取表中第42条记录即可。
问题：如果两个同学分别叫 刘丽 刘兰 该如何处理这两条记录？
这个问题是哈希表不可避免的，即冲突现象：对不同的关键字可能得到同一哈希地址。
二、哈希表的构造方法
１、直接定址法
例如：有一个从1到100岁的人口数字统计表，其中，年龄作为关键字，哈希函数取关键字自身。
地址
01
02
...
25
26
27
...
100
年龄
1
2
...
25
26
27
...
...
人数
3000
2000
...
1050
...
...
...
...
...
２、数字分析法
有学生的生日数据如下：
年.月.日
75.10.03
75.11.23
76.03.02
76.07.12
75.04.21
76.02.15
...
经分析,第一位，第二位，第三位重复的可能性大，取这三位造成冲突的机会增加，所以尽量不取前三位，取后三位比较好。
３、平方取中法
取关键字平方后的中间几位为哈希地址。
４、折叠法
将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址，这方法称为折叠法。
例如：每一种西文图书都有一个国际标准图书编号，它是一个10位的十进制数字，若要以它作关键字建立一个哈希表，当馆藏书种类不到10,000时，可采用此法构造一个四位数的哈希函数。如果一本书的编号为0-442-20586-4,则：
5864
5864
4220
0224
+)
04
+)
04
-----------
-----------
10088
6092
H(key)=0088
H(key)=6092
(a)移位叠加
(b)间界叠加
５、除留余数法
取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。
H(key)=key MOD p (p<=m)
６、随机数法
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即
H(key)=random(key) ,其中random为随机函数。通常用于关键字长度不等时采用此法。
三、总结
哈希表的优缺点
四、作业
预习如何处理冲突及哈希表的查找。
| 欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) |
黑马程序员IT技术论坛 X3.2 |