查找----基于散列表(拉链法)

上一篇:基于二叉查找树的查找

参照数据结构--符号表API实现。

使用散列表的查找算法分为两步:

  1. 用散列函数将被查找的键转化成数组索引
  2. 处理碰撞冲突

有两种常见的碰撞处理的方法,分别是拉链法和线性探测法

拉链法:将大小为M的数组中的每个元素指向一条结点类型的链表,链表中保存散列值为该元素的索引的键值对。

在一张含有M条链表和N个键的散列表中,未命中查找和插入操作需要的比较次数为~N/M。

拉链法的关键方法如下:

private int hash(Key key) {    //散列
	return (key.hashCode() & 0x7fffffff)%M;
}
public Value get(Key key) {    //查询
	return (Value) st[hash(key)].get(key);    //这里调用了链表的get()方法
}
public void put(Key key,Value val) {    //插入
	st[hash(key)].put(key, val);    //这里调用了链表的插入方法
}
public void delete(Key key) {    //删除
    if (key == null) throw new IllegalArgumentException("argument to delete() is null");
    int i = hash(key);
    if (st[i].contains(key)) N--;
    st[i].delete(key);    //这里调用了链表的删除方法
}

其中调用了链表的get()、put()、delete()方法。

散列表的大小问题。目标是既不会因为空链表太多而浪费大量内存,也不会因为链表太长而在查询方面耗费太长时间。可以动态调整数组大小以保持短小的链表。

下一篇:基于散列表(线性探测法)的查找

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏维C果糖

Guava 指南 之「使用和避免 null」

使用和避免null “null,糟糕透啦!” —— Doug Lea. “我称null为百亿美金的错误!” —— C. A. R. Hoare. 轻...

2117
来自专栏猿人谷

浅谈C/C++中的指针和数组(一)

                                                       浅谈C/C++中的指针和数组(一)       指...

2175
来自专栏抠抠空间

面对对象总结

一、类 1、类的定义 1 class 类名: 2 类属性 3 类方法 如: 1 class Person: 2 kind = '人类' ...

3339
来自专栏JMCui

读书笔记 之《Thinking in Java》(对象、集合、异常)

一、前言:     本来想看完书再整理下自己的笔记的,可是书才看了一半发现笔记有点多,有点乱,就先整理一份吧,顺便复习下前面的知识,之后的再补上。     真的...

3718
来自专栏深度学习自然语言处理

谈一谈python中的魔法变量*args和**kwargs

,没有注释,没有封装,没有可读性。哎,幸亏发现及时,现在正在写一个新的任务,刚好可以好好弄弄架构和代码了!

983
来自专栏Java帮帮-微信公众号-技术文章全总结

Java面试系列6

清明即事 帝里重清明, 人心自愁思。 车声上路合, 柳色东城翠。 花落草齐生, 莺飞蝶双戏。 空堂坐相忆, 酌茗聊代醉。 1.String是最基本的数据类型吗...

2715
来自专栏思考的代码世界

Python编程从入门到实践之遍历列表|第2天

通常情况下,我们需要对列表的所有元素进行操作,这个时候就需要遍历整个列表。循环采用for。

4287
来自专栏aCloudDeveloper

指向函数的指针

Author: bakari   Date: 2012.8.8 做好总结我觉得是把知识学扎实必不可少的实践环节。这个知识点是当初自己在学习这一块做的一些笔记,现...

1966
来自专栏Golang语言社区

Golang语言--细节汇总

slice和数组在声明时的区别:声明数组时,方括号内写明了数组的长度或使用...自动 计算长度,而声明slice时,方括号内没有任何字符。 对于slice有几个...

3699
来自专栏云霄雨霁

Java--对象的克隆

1627

扫码关注云+社区

领取腾讯云代金券