查找----基于散列表（拉链法）
参照数据结构--符号表API实现。
使用散列表的查找算法分为两步：
- 用散列函数将被查找的键转化成数组索引
- 处理碰撞冲突
有两种常见的碰撞处理的方法，分别是拉链法和线性探测法。
拉链法：将大小为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()方法。
散列表的大小问题。目标是既不会因为空链表太多而浪费大量内存，也不会因为链表太长而在查询方面耗费太长时间。可以动态调整数组大小以保持短小的链表。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017.12.16，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读