Hash面试总结

发表于 | 更新于: | 分类于 |
字数统计: 1.7k 字 | 阅读时长 ≈ 6 分钟

写在前面

大致总结了网上有关于hash 算法问题，包括hashmap和其他的一些扩展，还有些不完整。也有些东西不详细，而且虽然总结出来，其实也不是很了解，先行记录下来，慢慢去学。

1.什么是哈希

​ hash翻译为散列，或音译”哈希“

​ 把任意长度的输入(也叫预映射) 通过散列算法，变换成固定长度的输出，该输出就是散列值。

​ 这种转换是一种压缩映射，就是说散列值的空间通常小于输入空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一确定输入值。

​ 实际中的Hash函数是指把一个大范围映射到一个小范围。把大范围映射到一个小范围的目的往往是为了节省空间，使得数据容易保存。除此以外，Hash函数往往应用于查找、加密作用。

2.基本概念

散列表：若结构中存在和关键字K相等的记录，则必定在f(K)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function)，按这个思想建立的表为散列表

冲突 同义词

3.常用地构造函数方法

  • 直接寻址法 取key或者key的线性函数值作为散列地址
  • 数字分析法
  • 平方取中法
  • 折叠法
  • 随机数法
  • 除留余数法 取key被某个不大于散列表表长m的数p除后所得的余数为散列地址

4.冲突产生 - 处理冲突方式

​ 1.开放寻址法：(线性探索再散列 二次探测再散列 伪随机探测再散列)

​ 2.再散列法

​ 3.链地址法(拉链法)

​ 4.建立一个公共溢出区

5.Hash的时间复杂度

​ hash算法的复杂度 无冲突时hashtable复杂度为O(1) 一般是O(c) c为产生冲突时查找的平均长度。最坏情况仍然是O(n)

6.Hashmap 和 Hashtable的区别

主要区别在于Table加了线程保护

  • hashtable线程更加安全，代价就是因为他粗暴的添加了同步锁，所以会有性能损失
  • 有更好的concurrentHashMap可以代替HashTable
  • 存储：HashMap运行key和value为null，而Hashtable不允许
  • 线程安全：Hashtable 线程安全， HashMap非线程安全
  • 推荐使用：在Hashtable的类注释可以看到，Hashtable是保留类不建议使用，推荐在单线程环境下使用HashMap替代，如果需要多线程使用则用ConcurrentHashMap替代

7.如何决定使用Hashmap还是Treemap？

​ 对于在Map中插入，删除，定位一个元素这类操作，Hash Map是最好的选择，因为相对而言HashMap的插入会更快 ，但如果你要对一个key集合进行有序遍历，那么TreeMap是更好的选择。

8.Hashmap实现原理

​ HashMap基于Hash算法实现，通过put(key,value)存储，get(key)来获取，当传入key时，hashMap会根据key.hashCode()计算hash值，根据hash值将value保存在bucket中。当计算出的hash值相同的时候，则发生hash冲突。HashMap的做法使用链表和红黑树存储相同hash值的value，当冲突个数比较少的时候使用链表存储，否则使用红黑树。

​ 1.对key值进行hash计算

8+.说出Java中常用的哈希码(hashCode的)算法

  1. Object类的hashCode. 返回对象的经过处理后的内存地址，由于每个对象的内存地址都不一样，所以哈希码也不一样。这个是native方法，取决于JVM的内部设计，一般是某种C地址的偏移。
  2. String类的hashCode. 根据String类包含的字符串的内容，根hash据一种特殊算法返回哈希码，只要字符串的内容相同，返回的哈希码也相同。
  3. Integer等包装类，返回的哈希码就是Integer对象里所包含的那个整数的数值，例如Integer i1=new Integer(100), i1.hashCode的值就是100 。由此可见，2个一样大小的Integer对象，返回的哈希码也一样。
  4. int，char这样的基础类，它们不需要hashCode，如果需要存储时，将进行自动装箱操作，计算方法同上。

8++. hashCode()和equals()方法的重要性体现在什么地方？

Java中的HashMap使用hashCode()和equals()方法来确定键值对的索引，当根据键获取值的时候也会用到这两个方法。如果没有正确的实现这两个方法，两个不同的键可能会有相同的hash值，因此，可能会被集合认为是相等的。而且，这两个方法也用来发现重复元素。所以这两个方法的实现对HashMap的精确性和正确性是至关重要的。

  1. 获取到数组中index位置

    ​ 计算了Hash，我们现在要把它插入数组中了

    i = (table.length - 1) & hash；

    通过位运算，确定了当前的位置，因为HashMap数组的大小总是2^n，所以实际的运算就是 (0xfff…ff) & hash ，这里的tab.length-1相当于一个mask，滤掉了大于当前长度位的hash，使每个i都能插入到数组中。

  2. 生成包装类

  3. 插入包装类到数组

9.HashSet实现原理

HashSet基于HashMap实现的，HashSet底层使用HashMap来保存所有元素，因此HashSet的实现比较简单，相关HashSet的操作，基本上都是直接调用底层HashMap的相关方法来完成，HashSet不允许重复值。

10.如何提升hash的性能

  1. 解决扩容损失,如果知道大概需要的容量,把初始容量设置好以解决扩容损失;
  2. 解决碰撞损失:使用高效的HashCode和loadFactor JDK8的高性能提供了红黑树
  3. 解决数据结构选择的错误大型的数据与搜索中考虑使用别的数据结构比如TreeMap 需要key排序的时候建议使用TreeMap

11.jdk8中HashMap的新特性

如果某个桶中的链表记录过大的话（当前是TREEIFY_THRESHOLD = 8），就会把这个链动态变成红黑二叉树，使查询最差复杂度由O(N)变成了O(logN)。

1
2
3
4
5
6
7
8
9
10
11
12
//e 为临时变量，p为当前的链
for (int binCount = 0; ; ++binCount) {    
    if ((e = p.next) == null) {       
        p.next = newNode(hash, key, value, null);        
        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st            
            treeifyBin(tab, hash);        
        break;    
    }    
    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))        
        break;   
    p = e;
}

12.hash应用例子

0%