前几篇我们一起学习了基于数组、链表、二叉树、红黑树来实现Map的操作，本篇我们将会一起来学习基于散列表来实现Map，这种方式对应着java里面的HashMap，这也是使用最多的一种方式

散列表实现Map主要分为了两个步骤:

1. 基于散列函数将被查找键转换为数组的下标
2. 处理散列值冲突的情况，有两种方式来处理冲突：拉链式和线性探测

散列函数

实现散列表的第一步就是需要考虑如何把一个键转换为数组的下标，这时候就需要使用到散列函数，先把键值转换成一个整数然后在使用除留余数法计算出数组的下标。每种类型的键我们都需要一个不同的散列函数。

在java中对于常用的数据类型已经实现了hashCode，我们只需要根据hashCode的值使用除留余数法即可转换成数组的下标

java中的约定：如果两个对象的equals相等，那么hashCode一定相同;如果hashCode相同，equals不一定相同。对于自定义类型的键我们通常需要自定义实现hashCode和equals;默认的hashCode返回的是对象的内存地址，这种散列值不会太好。

下面我来看看Java中常用类型的hashCode计算方式

Integer

由于hashCode需要返回的值就是一个int值，所以Integer的hashCode实现很简单，直接返回当前的value值

1. @Override 
2. public int hashCode() { 
3.     return Integer.hashCode(value); 
4. } 
5. public static int hashCode(int value) { 
6.     return value; 
7. } 

Long

Java中Long类型的hashCode计算是先把值无符号右移32位，之后再与值相异或，保证每一位都用用到，最后强制转换成int值

1. @Override 
2. public int hashCode() { 
3.     return Long.hashCode(value); 
4. } 
5.  
6. public static int hashCode(long value) { 
7.     return (int)(value ^ (value >>> 32)); 
8. } 

Double、Float

浮点类型的键java中hashCode的实现是将键表示为二进制

1. public static int hashCode(float value) { 
2.     return floatToIntBits(value); 
3. } 
4. public static int floatToIntBits(float value) { 
5.     int result = floatToRawIntBits(value); 
6.     // Check for NaN based on values of bit fields, maximum 
7.     // exponent and nonzero significand. 
8.     if ( ((result & FloatConsts.EXP_BIT_MASK) == 
9.           FloatConsts.EXP_BIT_MASK) && 
10.          (result & FloatConsts.SIGNIF_BIT_MASK) != 0) 
11.         result = 0x7fc00000; 
12.     return result; 
13. } 

String

java中每个char都可以表示成一个int值，所以字符串转换成一个int值