1、哈希表基础 参考LeetCode第387号问题：给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。提示：你可以假定该字符串只包含小写字母。 这种方法的时间复杂度是O(n)
public int firstUniqChar(String s) { int[] freq = new int[26]; //先将字符串中各个字母出现的频率存储到freq数组（数组下标对应字母在ASCII表中26个小写字母中的位置） for (int i = 0; i < s.length() ; i++) { freq[s.charAt(i) - 'a']++; } for (int i = 0; i < s.length() ; i++) { if(freq[s.charAt(i) - 'a'] == 1) return i; } return -1; }哈希表2个核心问题： 1）对于我们关注的内容（这里是字符），必须将其转换为索引。我们使用哈希函数将各类数据转换为索引；（哈希函数设计） 2）我们将不同的“键”转换为索引的时候，很难找到某个哈希函数，使得不同“键”可以转换成为不同的“索引”，很多时候，不同的“键”可能转换为同一个“索引”，这个时候就要我们解决哈希冲突！（解决哈希冲突）
2、哈希函数的设计
3、java中的 hashCode() 方法 代码如下：
-----Student类
package com.lkj; public class Student { int grade; int cls; String firstName; String lastName; Student(int grade, int cls, String firstName, String lastName){ this.grade = grade; this.cls = cls; this.firstName = firstName; this.lastName = lastName; } /** 如果我们想使得Student类能够哈希，我们必须实现hashCode()方法 如果Student不实现hashCode()方法，依然可以运行程序，这是因为Object默认有一个hashCode()实现， 这个hashCode()方法是根据地质来计算哈希值。 */ @Override public int hashCode(){ int B = 31;//31，就是第二节所说的进制。这里素数M还没有取到，我们先不计算M（M代表哈希表数组的大小） int hash = 0; hash = hash * B + grade; hash = hash * B + cls; hash = hash * B + firstName.toLowerCase().hashCode();//加toLowerCase()用于忽略大小写，大小写表示同一个人 hash = hash * B + lastName.toLowerCase().hashCode(); return hash; } /** 如果不同的“键”映射到同一个哈希值，产生哈希冲突，这时就要真正的比较2个“键”的值， 因此我们还需要实现equals()方法 */ @Override public boolean equals(Object o) { if(o == this) return true;//2个对象的引用相同，同一个Student if(o == null) return false;//空对象，直接返回false if(this.getClass() != o.getClass()) return false;//2个对象的类对象不同，肯定不是同一个对象，返回false //以上判断都通过，那么就根据2个对象的各个属性是否相同来判断他们是不是同一个对象 Student another = (Student)o; //这里，基本数据类型用“==” 边角是否相等，引用数据类型用 equals() 方法比较是否相等 return this.grade == another.grade && this.cls == another.cls && this.firstName.toLowerCase().equals(another.firstName.toLowerCase()) && this.lastName.toLowerCase().equals(another.lastName.toLowerCase()); } }Main方法的测试见源码。
4、哈希冲突的解决-链地址法
5、实现哈希表+哈希表动态空间处理+哈希表时间复杂度分析
哈希表使用动态数组后的时间复杂度分析： 哈希表的代码如下：
package com.lkj; import java.util.TreeMap; /** 注意，哈希表的键不需要具有比较性，但是他的键需要实现 hashTable() 与 equals() 方法， 由于每一个键类型都会继承Object类，因此都继承Object的 hashCode() 与 equals() 方法，d 当然，我们自己也可以重写自己需要的 hashCode() 与 equals() 方法。 */ public class HashTable<K , V> { //首先，定义一个数组，数组内存储TreeMap类型的数据，然后TreeMap内存储的才是相应的键值数据 private TreeMap<K,V>[] hashtable; private int M;//定义数组的长度，素数 private int size;//数组内存储的键值对的个数 //定义2个常量用于扩容操作，这两个常量表示每个位置的平均哈希冲突数量（即数组每个位置查找表的元素数量） private static final int upperTol = 10; private static final int lowerTol = 2; // private static final int initCapacity = 7;//初始化容量 //我们使用一个素数表来定义哈希表数组的扩容与缩容，这样可以避免更多的哈希冲突 private final int[] capacity = {53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741}; private int capacityIndex = 0;//用于获取capacity数组的值，初始为0 public HashTable() { this.M = M; size = 0; hashtable = new TreeMap[capacityIndex];//初始化数组的长度 //对于数组内的每一个元素，都是TreeMap对象，我们需要初始化这些对象 for (int i = 0; i < M ; i++) { hashtable[i] = new TreeMap<>(); } } // public HashTable() // { // this(initCapacity);//默认使用97作为素数 // } public int getSize() { return size; } //辅助方法，使用这个哈希方法，将传入的 key值 转换为 hashtable 数组内的索引 private int hash(K key)//注意，这个key可以是任意类型 { //先利用key的哈希方法，将key转换为整数，再将整数转换为正数，随后除以M获得其在哈希数组内的索引 return (key.hashCode() & 0x7fffffff) % M; } //添加方法 public void add(K key , V value) { //先求得key在数组内的位置 hash(key)，并找到这个位置的TreeMap TreeMap<K, V> map = hashtable[hash(key)]; /** 如果这个位置的 TreeMap 已经原来已经存储了这个key，那么我们将这个key的value值直接覆盖原来key的value 如果这个位置的 TreeMap 已经原来没有存储这个key，我们将这个键值对存储进去即可。 如果有多个不同的 key 的哈希值都是这个位置的值，我们将这些哈希值相同的 key 存储到同一个位置的TreeMap中即可 */ if(map.containsKey(key)) { map.put(key , value);//覆盖value } else { map.put(key , value);//添加键值对 size++; /** 当哈希表每个位置的元素数量（哈希冲突）大于 upperTol 的时候，扩容数组 */ // if(size/M >= upperTol) //将乘法转换为除法，避免浮点型与整形的转换. //注意capacity数组不能越界 if(size >= upperTol*M && capacityIndex+1 < capacity.length) { capacityIndex++; resize(capacity[capacityIndex]); } } } //删除 public V remove(K key) { TreeMap<K, V> map = hashtable[hash(key)]; V ret = null; if(map.containsKey(key)) { ret = map.remove(key); size--; //控制缩容过程中哈希表数组的长度大于初始的容量 if(size < lowerTol*M && capacityIndex-1 >= 0) { capacityIndex--; resize(capacity[capacityIndex]); } } return ret; } //设置键的值 public void set(K key , V value) { TreeMap<K, V> map = hashtable[hash(key)]; if(!map.containsKey(key)) throw new IllegalArgumentException(key + " doesn't exist!"); map.put(key , value); } //查询是否包含某个键 public boolean contains(K key) { return hashtable[hash(key)].containsKey(key); } //获取某个键的值 public V get(K key) { return hashtable[hash(key)].get(key); } //扩容方法 private void resize(int newM) { //重新创建一个 TreeMap类型的数组 TreeMap<K,V>[] newHashTable = new TreeMap[newM]; //初始化新的 TreeMap 数组每一个位置的TreeMap for (int i = 0; i < newM ; i++) newHashTable[i] = new TreeMap<>(); /** 下面，将原来 TreeMap 数组中的元素存储到新的数组中 注意，下面 newHashTable[hash(key)].put(key , map.get(key)) 中，hash(key) 方法中使用到M，而这里使用的M是我们类中 定义的M，但是事实上，这里newHashTable应该使用新传入的 newM，使用旧的M会使得获取到新的哈希表数组的所有不均匀。 那么我们应该事先更新类的M为newM. 下面遍历中药使用到旧的M，因为将原来 hashtable 中的元素转换为新的 newHashTable中， 原来 hashtable 的长度就是旧的M，因此需要将旧的M保存起来 */ int oldM = M; this.M = newM; for (int i = 0; i < oldM ; i++) { TreeMap<K, V> map = hashtable[i];//先取出老的 TreeMap 数组 hashtable 每一个位置的TreeMap //取出TreeMap中的元素，存储到新的TreeMap数组 newHashTable 相应的位置 for (K key : map.keySet()) newHashTable[hash(key)].put(key , map.get(key)); } this.hashtable = newHashTable;//将原来的hashtable更新为新的newHashTable } }6、更多哈希冲突的解决方法
