Android|『查漏补缺』Android实习面试知识点（二）面试|java|哈希算法|面试

『查漏补缺』Android实习面试知识点（二）

个人语录：人生的艰难困苦我们无法选择，但是可以选择让自己无坚不摧，战无不胜，时间不负有心人，星光不问赶路人

文章目录

『查漏补缺』Android实习面试知识点（二）
- 为什么大部分 hashcode 方法使用 31
- - hash是什么
  - hashcode是啥
  - 为什么使用 HashCode
- HashMap 的 hash 算法的实现原理（为什么右移 16 位，为什么要使用 ^ 位异或）
- 手写HashMap

为什么大部分 hashcode 方法使用 31 看一段String类的hash代码：

public int hashCode() { int h = hash; if (h == 0 && value.length > 0) { char val[] = value; for (int i = 0; i < value.length; i++) { h = 31 * h + val[i]; } hash = h; } return h; }

答案：
之所以使用 31，是因为他是一个奇素数。如果乘数是偶数，并且乘法溢出的话，信息就会丢失，因为与2相乘等价于移位运算（低位补0）。使用素数的好处并不很明显，但是习惯上使用素数来计算散列结果。 31 有个很好的性能，即用移位和减法来代替乘法，可以得到更好的性能： 31 * i == (i << 5） - i，现代的 JVM 可以自动完成这种优化。这个公式可以很简单的推导出来。
hash是什么
hash是一个函数，该函数中的实现就是一种算法，就是通过一系列的算法来得到一个hash值，这个时候，我们就需要知道另一个东西，hash表，通过hash算法得到的hash值就在这张hash表中，也就是说，hash表就是所有的hash值组成的，有很多种hash函数，也就代表着有很多种算法得到hash值, 编写散列函数是老生常谈的研究课题，是数学家和理论方面的计算机科学家的研究任务, 我们只需要知道那些比较好用, 大概为啥好用就可以了
hashcode是啥
hashcode就是通过hash函数得来的，通俗的说，就是通过某一种算法得到的，hashcode就是在hash表中有对应的位置。
每个对象都有hashcode，对象的hashcode怎么得来的呢？
首先一个对象肯定有物理地址，网上有人把对象的hashcode说成是对象的地址，事实上这种看法是不全面的，确实有些JVM在实现时是直接返回对象的存储地址，但是大多时候并不是这样，只能说可能存储地址有一定关联,
那么对象如何得到hashcode呢？通过对象的内部地址(也就是物理地址)转换成一个整数，然后该整数通过hash函数的算法就得到了hashcode(不同jvm的实现不同, hotspot的实现贴在了最后)，所以，hashcode是什么呢？就是在hash表中对应的位置。这里如果还不是很清楚的话，举个例子，hash表中有 hashcode为1、hashcode为2、(…)3、4、5、6、7、8这样八个位置，有一个对象A，A的物理地址转换为一个整数17(这是假如)，就通过直接取余算法，17%8=1，那么A的hashcode就为1，且A就在hash表中1的位置。
为什么使用 HashCode
HashCode的存在主要是为了查找的快捷性, HashCode是用来在散列存储结构中确定对象的存储地址的 ( 用hashcode来代表对象在hash表中的位置 ) , hashCode 存在的重要的原因之一就是在 HashMap(HashSet 其实就是HashMap) 中使用（其实Object 类的 hashCode 方法注释已经说明了），HashMap 之所以速度快，因为他使用的是散列表，根据 key 的 hashcode 值生成数组下标（通过内存地址直接查找，不需要判断, 但是需要多出很多内存，相当于以空间换时间）
HashMap 的 hash 算法的实现原理（为什么右移 16 位，为什么要使用 ^ 位异或）

看一下HashMap的hash算法实现

static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

==抛出一个问题：==乍看一下就是简单的异或运算和右移运算，但是为什么要异或呢？为什么要移位呢？而且移位16？
先看看：HashMap 如何根据 hash 值找到数组中的对象，我们看看 get 方法的代码：

final Node getNode(int hash, Object key) { Node[] tab; Node first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && // 我们需要关注下面这一行 (first = tab[(n - 1) & hash]) != null) { if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode)first).getTreeNode(hash, key); do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }

我们看看代码中注释下方的一行代码：first = tab[(n - 1) & hash]。
使用数组长度减一与运算 hash 值。这行代码就是为什么要让前面的 hash 方法移位并异或。
我们分析一下：
首先，假设有一种情况，对象 A 的 hashCode 为 1000010001110001000001111000000，对象 B 的 hashCode 为 0111011100111000101000010100000。
如果数组长度是16，也就是 15 与运算这两个数，你会发现结果都是0。这样的散列结果太让人失望了。很明显不是一个好的散列算法。
但是如果我们将 hashCode 值右移 16 位，也就是取 int 类型的一半，刚好将该二进制数对半切开。并且使用位异或运算（如果两个数对应的位置相反，则结果为1，反之为0），这样的话，就能避免我们上面的情况的发生。
总的来说，使用位移 16 位和异或就是防止这种极端情况。但是，该方法在一些极端情况下还是有问题，比如：10000000000000000000000000 和 10000000001000000000000000 这两个数，如果数组长度是16，那么即使右移16位，在异或，hash 值还是会重复。但是为了性能，对这种极端情况，JDK 的作者选择了性能。毕竟这是少数情况，为了这种情况去增加 hash 时间，性价比不高。
手写HashMap

现在的面试越来越内卷了，手写HashMap被提出来了，那咋就开整

下面的实现不会很难，是JDK1.7 版本的HashMap的简化版，估计面试官不会问你更加复杂的红黑树实现，毕竟一个面试不能这么难的

参考：
漫画：什么是红黑树？（整合版）
HashMap源码&底层数据结构分析
手写HashMap，快手面试官直呼内行

直接贴源码

import java.security.Key; public class HashMapMini { /* * 节点类 **/ class Node{ /*键值对*/ private K key; private V value; /*链表的后继结点*/ private Node next; public Node(K key, V value) { this.key = key; this.value = https://www.it610.com/article/value; }public Node(K key, V value, Node next) { this.key = key; this.value = https://www.it610.com/article/value; this.next = next; } }/*默认容量*/ final int DEFAULT_CAPACITY = 16; /*负载因子*/ final float LOAD_FACTOR = 0.75f; /*HashMap的大小*/ private int size; /*桶数组*/ private Node[] buckets; /* * 无参构造，指定桶数组的大小为默认容量 * */public HashMapMini() { buckets = new Node[DEFAULT_CAPACITY]; size = 0; }/* * 有参构造 * */ public HashMapMini(int capacity) { buckets = new Node[capacity]; size = 0; }/* * 哈希函数，获取地址 * */ private int getIndex(K key,int length){ /*获取hashcode*/ int hashcode = key.hashCode(); /*和桶数组长度取余数*/ int index = hashcode%length; return Math.abs(index); }/* * put方法 * */ public void put(K key,V value){ // 是否需要扩容 if (size>=buckets.length*LOAD_FACTOR) resize(); putVal(key,value,buckets); }/* * 将元素存入指定的Node数组 * */ private void putVal(K key,V value,Node[] table){ /*获取位置*/ int index = getIndex(key,table.length); Node node = table[index]; /*插入位置为空*/ if (node==null){ table[index] = new Node<>(key,value); size++; return; } /*插入位置不为空，说明发生冲突，使用链地址法，遍历链表*/ while (node!=null){ /*如果key相同就覆盖掉原先的值*/ if ((node.key.hashCode()==key.hashCode())&&(node.key==key||node.key.equals(key))){ node.value = https://www.it610.com/article/value; return ; } node = node.next; } /*当key不在链表中，插入链表头部*/ Node newNode = new Node(key,value,table[index]); table[index] = newNode; size++; }/* * 扩容*/ private void resize(){ /*创建一个两倍容量的桶数组*/ Node[] newBuckets = new Node[buckets.length<<1]; /*将当前元素重新散列到新的桶数组里面*/ rehash(newBuckets); buckets = newBuckets; }/* * 重新散列当前元素*/ private void rehash(Node[] newBuckets) { /*map的大小重新计算*/ size=0; /*将旧的桶数组再次哈希到新的数组里面*/ for (int i=0; i node = buckets[i]; while (node!=null){ putVal(node.key,node.value,newBuckets); node = node.next; } } }/* * 获取元素*/ public V get(K key){ // 获取key对应的地址 int index = getIndex(key,buckets.length); if (buckets[index]==null) return null; Node node = buckets[index]; // 查找链表 while (node!=null){ if ((node.key.hashCode()==key.hashCode())&&(node.key==key||node.key.equals(key))){ return node.value; } node =node.next; } return null; }/* * 返回HashMap的大小 * */ public int size(){ return size; }public int getBucketsSize(){ return buckets.length; }}

【Android|『查漏补缺』Android实习面试知识点（二）】Test：