散列表：其实相当于就是一种可以存储键值的数据结构
咱们先把散列表当成一个数组来看
键就相当于是数组索引，值就是索引内存上对应的数据
我们利用一种建议的扩展来处理更加复杂的键，利用算数操作
将键转化成数组发的索引 然后来访问数组的键值对
正常来说将查找分成俩步:
1.用散列算法 将别的类型的键转换数组的索引
int index = hashToIndex(str);
但是上述的算法 十分容易碰到散列冲突的状况
比如说当上述 虽然str不同 但是算出来的index 都是一样的
如果要解决这种冲突 我们应该是给数组扩容 然后扩大散列的范围
但是这样就会有空间内存的问题，然后散列表相当于以一个合理的方式
解决了这种问题。
下面我们会简单介绍一下俩种解决这种冲突的方法:
拉链法和线性探测法
散列函数：散列函数应该是能够计算并均匀分布所有键，
举一个简单的例子，比如一个简单的证件:203-202-1111
假设我们大致有个几千人，我们可以以前三位作为散列
然后开辟一个1000个长度的数组，然后前三位当索引去存储
如果前三位冲突会在后续说明解决冲突的办法。这里只是举一个
简单的例子，正常情况应该以这10位数运算出一个散列值
散列最常用的方法为除留余数法，直接以转换过的散列数%数组
长度即可 ，但是如果数组长度不是素数，会导致我们无法
均匀的分布散列，大家可思考一下就像比如说数组长度是100
2 5 10 。。。 都取余100 为0
处理字符串的话 java可以把其转换成字符，然后将散列值
相加，最后用取余，但是要防止溢出
image.png
简单介绍一下正常java种hash的处理
java要是自定义散列函数的话，需要重写hashCode和equals
方法 默认hashcode 会返回对象内存地址
image.png
java种的String,Integer Double File URL 的HashCode 都实现了自己
定义hash 使其值分配的很均匀
其实最简单的做法 就是把java 对象中的所有引用类型的变量
image.png
然后如果总是计算散列耗性能的话，我们可以就在最开始计算一次
然后之后返回的都是之前记录的值，这样就不会对性能开销很大。
总结 一个优秀的散列方法 需要满足三个条件:
1.一致性 等价的键散列必相同
2.高效性 计算简便
3.均匀性 散列值需要均匀散列所有的键
当然这些设计都是专家可以做的 ，java 就只调用hashcode 就可以了
但是对性能有要求的情况 要谨慎的用散列
因为散列的计算还是比较耗时的
设计散列函数时指定的散列结果范围的参数一定要慎重，
要避免大量的碰撞，
基于拉链法的散列表
第一步 将键通过散列变成数组索引，第二，如果当前索引
已经有数据存储，这样就是我们俗称的碰撞，我们就可以
将当前数据 变成一个链表，然后在数组中存放该链表对象
如果有碰撞就将链表节点增加，然后去添加数据。
简单的给大家实现了个小demo
public class HashST<Key,Value>{
private int N;//键值对数据大小
private int M;//散列大小
private Node[]st;
public HashST(int M){
this.M = M;
st = new Node[M];
}
private int hash(Key key){
return (key.hashCode() & 0x7ffffff)%M;
}
public Value get(Key key){
Node n = st[hash(key)];
while (n != null){
if(n.key == key)
return n.value;
n = n.next;
}
return null;
}
public void put(Key key,Value val){
Node n = new Node(key,val);
Node prev = st[hash(key)];
if(prev == null){
st[hash(key)]= n;
}else{
while (prev.next!=null){
prev = prev.next;
}
prev.next =n;
}
}
private class Node{
Key key;
Value value;
Node next;
public Node(Key key,Value value){
this.key = key;
this.value = value;
}
}
网友评论