浅谈哈希
什么是哈希?
哈希简单来说就是输入一个数,得到另一个数的过程,这个过程中最关键的部分就是哈希函数(也叫哈希算法)。哈希算法并不指代某一特定的算法,典型的哈希算法包括 MD2、MD4、MD5 和 SHA-1
哈希要求
不同的输入要产生不同的值
哈希函数
哈希函数的好坏直接影响到生成的值碰撞的概率,碰撞概率越小,哈希函数构造得越好
常用哈希函数的构造方法
- 直接定址法
- 数据分析法
- 折叠法
- 平方取中法
解决冲突
虽然我们不希望产生冲突,但发生冲突的可能性是存在的,当我们的key值域远远大于哈希表的长度时冲突很可能发生
我们可以采用以下方式来解决冲突:
- 开放定址法:当一个关键字和另一个关键字发生冲突时,在数组中另找一个可用的地址,而不是通过哈希函数计算得到的地址
- 链地址法:当发冲突时,将所有哈希值相同的关键字链接在以该哈希地址为表头指针的链表中,采用这种方法永远不会产生溢出现象,因为链表会在新加入关键字后扩展(这是HashMap采用的方法)
hashCode()
hashCode()是java中的哈希函数,所有的哈希都是由这个函数来实现。它是一个本地方法,它的实现与本地机器有关。这个方法存在于Object.class
中
public native int hashCode();
hash()
HashMap里的扰动函数,目的是为了减小冲突概率。
哈希的优势
数组是java中效率最高的数据结构,但是“最高”是有前提的。第一我们需要知道所查询数据的所在位置。第二:如果我们进行迭代查找时,数据量一定要小,对于大数据量而言一般推荐集合。
在Java集合中有两类,一类是List
,一类是Set
他们之间的区别就在于List集合中的元素师有序的,且可以重复,而Set集合中元素是无序不可重复的。对于List好处理,但是对于Set而言我们要如何来保证元素不重复呢?通过迭代来equals()
是否相等。数据量小还可以接受,当我们的数据量大的时候效率可想而知(当然我们可以利用算法进行优化)。比如我们向HashSet插入1000数据,难道我们真的要迭代1000次,调用1000次equals()
方法吗?hashCode()
提供了解决方案。怎么实现?
这里我们暂且认为他返回的是对象存储的物理位置(实际上不是,这里写是便于理解)。当我们向一个集合中添加某个元素,集合会首先调用hashCode方法,这样就可以直接定位它所存储的位置,若该处没有其他元素,则直接保存。若该处已经有元素存在,就调用equals方法来匹配这两个元素是否相同,相同则不存,不同则散列到其他位置。这样处理,当我们存入大量元素时就可以大大减少调用equals()方法的次数,极大地提高了效率。
哈希算法的应用
- 加密
- 容器(如
HashMap
)