用关键字序列{7,8,34,11,18,9,14,25}构造一个哈希表
时间: 2024-06-05 18:10:47 浏览: 15
构造哈希表的一般步骤:
1.选择哈希函数;
2.创建一个数组,大小为哈希表中预计的元素数量;
3.将每个关键字通过哈希函数转换为一个索引值,并将该值放入数组中对应的位置。
具体操作步骤如下:
1.选择哈希函数:采用简单的取模哈希函数 h(key) = key % n,其中 n 为数组大小;
2.创建一个大小为8的数组 table;
3.将关键字序列 {7, 8, 34, 11, 18, 9, 14, 25} 依次插入哈希表中:
- 7 % 8 = 7,将 7 存入 table[7] 中;
- 8 % 8 = 0,将 8 存入 table[0] 中;
- 34 % 8 = 2,将 34 存入 table[2] 中;
- 11 % 8 = 3,将 11 存入 table[3] 中;
- 18 % 8 = 2,发生冲突,采用开放地址法解决,将 18 存入 table[3+1] = table[4] 中;
- 9 % 8 = 1,将 9 存入 table[1] 中;
- 14 % 8 = 6,将 14 存入 table[6] 中;
- 25 % 8 = 1,发生冲突,采用线性探测法解决,将 25 存入 table[1+1] = table[2] 中。
最终的哈希表如下:
|table[0]|table[1]|table[2]|table[3]|table[4]|table[5]|table[6]|table[7]|
|--------|--------|--------|--------|--------|--------|--------|--------|
| 8 | 9 | 34 | 11 | 18 | | 14 | 7 |