该方式即为哈希
(
散列
)
方法，
哈希方法中使用的转换函数称为哈希
(
散列
)
函数，构造出来的结构称为哈希表
(Hash
Table)(
或者称散列表
)
哈希冲突
什么是哈希冲突
对于两个数据元素的关键字 和
(i != j)
，有
!=
，但有：
Hash( ) == Hash( )
，即：
不同关键字通过相同哈
希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞
。
怎样解决哈希冲突
1、闭散列（线性探测）：当冲突发生时，找到冲突旁边的空闲位置放入冲突元素
缺点：通过这种方式解决哈希冲突，当被冲突元素所占位置需要插入元素时，该位置已经不能被插入，那就需要继续查找空闲位置，这样的话，不仅插入的效率会降低，查询的效率也会降低，而且还会影响其他元素的插入与查询。
2、开散列：当冲突发生时将冲突位置变为一个链表。
缺点：当某一个为值发生的冲突过多，会导致链表长度过长，由此带来插入和查询效率降低。
哈希函数
常用的哈希函数
1. 直接定制法
取关键字的某个线性函数为散列地址：
Hash
（
Key
）
= A*Key + B
优点：简单、均匀 缺点：需要事先知道关
键字的分布情况 使用场景：适合查找比较小且连续的情况 。
2. 除留余数法
设散列表中允许的
地址数为
m
，取一个不大于
m
，但最接近或者等于
m
的质数
p
作为除数，按照哈希函数：
Hash(key) = key% p(p<=m),
将关键码转换成哈希地址。
3. 平方取中法
假设关键字为
1234
，对它平方就是
1522756
，抽取中间的
3
位
227
作为哈希地址； 再比如关键字为
4321
，对 它平方就是18671041
，抽取中间的
3
位
671(
或
710)
作为哈希地址
平方取中法比较适合：不知道关键字的分
布，而位数又不是很大的情况。
4. 折叠法
折叠法是将关键字从左到右分割成位数相等的几部分
(
最后一部分位数可以短些
)
，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况。
5.
随机数法
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即
H(key) = random(key),
其中
random
为随机数函数。
通常应用于关键字长度不等时采用此法
6. 数学分析法
设有
n
个
d
位数，每一位可能有
r
种不同的符号，这
r
种不同的符号在各位上出现的频率不一定相同，可能在某 些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。
注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突
设计哈希表
在哈希表的设计中我采用开散列来解决哈希冲突，而哈希函数采用的是除留余数法。
哈希表模块设计
1、哈希函数
private int hash(int key) {
return key % this.M;
}
哈希函数是哈希表中最重要的一部分，一个好的哈希函数可以大大降低哈希冲突产生的概率，我采用的是哈希函数是对哈希桶的长度进行取余操作。
2、添加元素
public int put(int key,int value) {
// 1.首先计算出当前新元素的下标
int index = hash(key);
// 2.在当前的子链表中判断key值是否存在，若存在，只需要更新value即可
for (Node x = data[index];x != null;x = x.next) {
if (x.key == key) {
// 存在，只需要更新value
int oldValue = x.value;
x.value = value;
return oldValue;
}
}
// 3.此时key第一次出现，头插到当前的子链表中
Node node = new Node(key,value);
node.next = data[index];
data[index] = node;
size ++;
// 4.判断当前哈希表的冲突情况，是否需要扩容
if (size >= this.data.length * LOAD_FACTOR) {
resize();
}
return -1;
}
先计算出元素hash后的值，作为索引下标，在判断当前索引链表是否存在key值，若不存在直接插入（头插到链表中），若存在返回旧的value值，并更新value值。并判断是否需要对哈希表进行扩容。
3.扩容
private void resize() {
this.M = data.length << 1;
Node[] newData = new Node[data.length << 1];
// 搬移原数组的所有节点
for (int i = 0; i < data.length; i++) {
for (Node x = data[i];x != null;) {
Node next = x.next;
// 当前x搬移到新数组的对应位置
int newIndex = hash(x.key);
// 头插到新数组的对应位置
x.next = newData[newIndex];
newData[newIndex] = x;
// 继续搬移原数组的下一个节点
x = next;
}
}
// 更新data的指向
data = newData;
}
当哈希表需要扩容时，先将哈希桶扩容为原来的二倍，之后因为原来哈希表中的所以是根据哈希桶的长度取余所得，所以需要对之前的元素进行搬移。
哈希表的实现
public class MyHashMap {
private class Node{
int key;
int value;
Node next;
public Node(int key,int value) {
this.key = key;
this.value=value;
}
}
private int size;
private int m;
private Node[] data;
private static final double LOACL_FACTOR = 0.75;
public MyHashMap() {
this(16);
}
public MyHashMap(int capacity){
this.data=new Node[capacity];
this.m=capacity;
}
public int put(int key,int value){
int index=hash(key);
for(Node x=data[index];x!=null;x=x.next){
if(x.key==key){
int oldval=x.value;
x.value=value;
return oldval;
}
}
Node node=new Node(key,value);
node.next=data[index];
data[index]=node;
size++;
if(size>=data.length*LOACL_FACTOR){
resize();
}
return -1;
}
private void resize(){
this.m= data.length<<1;
Node[] newData=new Node[data.length<<1];
for(int i=0;i<data.length;i++){
for(Node x=data[i];x!=null;){
Node next=x.next;
int newIndex=hash(x.key);
x.next=newData[newIndex];
newData[newIndex]=x;
x=next;
}
}
data=newData;
}
public boolean removeKey(int key){
int index=hash(key);
if(data[index]==null){
return false;
}
if (data[index].key == key) {
data[index] = data[index].next;
size --;
return true;
}
Node prev=data[index];
while(prev.next!=null){
if(prev.next.key==key){
prev.next=prev.next.next;
size--;
return true;
}
}
return false;
}
public boolean cntainsKey(int key){
int index=hash(key);
for(Node x=data[index];x!=null;x=x.next){
if(x.key==key){
return true;
}
}
return false;
}
public boolean containsValue(int value){
for(int i=0;i<data.length;i++){
for(Node x=data[i];x!=null;x=x.next){
if(x.value==value){
return true;
}
}
}
return false;
}
private int hash(int k){
return k%m;
}
}
