哈希取模java,哈希取模分表

本文目录一览：

• 1、java 1.哈希算法的实现：
• 2、java哈希值
• 3、java里的取模
• 4、java取模运算
• 5、Hash冲突的解决方法

java 1.哈希算法的实现：

public class Test { /*创建类*/

public static void main(String[] args) {

System.out.println(dg(100));

}

static int dg(int i) { /*定义变量 */

int sum;

if (i == 1) /*假设条件*/

return 1;

else

sum = i + dg(i – 1); /*1~100的和的表达式*/

return sum; /*返回结果*/

}

}

这个脚本语言为 Internet 应用而生，它可以看作是 Haskell 和 Java 的结合。

java哈希值

两个内容相同的对象具有相同的hashcode；反之不成立。

HashMap对象是根据其Key的hashCode来获取对应的Value。

map的实现是数组结合链表。hashcode决定存放位置，两个对象位置一样时比较equals方法。true的话覆盖（同一个对象），false的添加（不是同一个对象）。

java里的取模

%是取模运算，结果是余数，和/(除)可以对比。java中int做除运算会把小数部分直接去掉。

7/5=1 （余2） 7%5=2

12345/10=1234 （余5） 12345%10=5

java取模运算

如图，结果分别是1,1，-1,-1

按照我的理解，a%b的结果c就是在（-|b|,|b|）内的a+kb值，k是整数,c的正负取决于a的正负

Hash冲突的解决方法

哈希非哈希区别在于关键字在表中位置和它之间是否存在一个确定关系，哈希存在，非哈希不存在。

hash就是散列，就是把任意长度的输入，通过散列算法，变成固定长度的输出，输出就是散列值，该转换是压缩转换，散列值空间远小于输入的空间，不同的输入可能会散列成相同的输出。

Hash冲突，也就是经过一个函数结果作为地址去存放当前key value键值对(这个是hashmap存值方式)。

解决hash冲突发方法有

1）开放定址法，m为表长度，增量di有三种取法，线性探测再散列，平方探测再散列。

2）链地址法，就是key值取模再运算，java的HashMap就是这么实现的，在put()方法里面。

3）重哈希法，在创建hashmap的时候一般默认初始化容量，创建的hash表是桶的数量，负载因子：map的size/初始化容量，当hash表中负载因子达到负载极限，hash表会自动成倍增加容量，并将原有的对象重新分配加入新的值，成为rehash，rehash非常影响性能，所以初始化容量要设置好，不能太过浪费空间，也不能过小造成rehash情况经常出现。

4）建立一个公共溢出区域，就是把冲突的都放在另一个地方，不在表里面。

先看HashMap的数据结构，HashMap的底层主要是基于数组和链表来实现的，它之所以有相当快的查询速度主要是因为它通过计算散列码来决定存储的位置，HashMap中主要是通过key的hashCode来计算hash值的，只要hashCode相同，出来的hash值一样，不同对象出来的hash值一样，出现所谓hash冲突，HashMap底层通过链表解决hash冲突的。

HashMap其实就是一个Entry数组（类似pair），Entry对象中包含了链和值，其中next也是一个Entry对象，它就是用来处理hash冲突的，形成一个链表。

在Java8之前，如果发生hash冲突往往是将该value直接链接到该位置的其他所有value的头部，即相互冲突的所有value形成一个链表，因此，最坏情况HashMap的查找时间复杂度退化到O(n)，在Java8中做了改进，一个是改头插法为尾插法，还有一个是当一个位置冲突过多时（大于等于8），存储的value将形成一排序二叉树，排序的依据为key的hashCode，这样在最坏情况下，性能也只退化到O(logn)。

这样的改进意义重大，一是从O(n)提升到O(logn)的时间开销（最坏情况），二是如果恶意程序知道我们利用的Hash算法，在纯链表情况下，发送大量请求导致hash碰撞，不停访问这些key使HashMap忙于查找，最终瘫痪。