数据结构之哈希表

1. 哈希表

不考虑顺序、不考虑Key的比较性，使用哈希表实现映射平均复杂度甚至可以到达O(1)，一个典型的空间换时间，又称散列表。

使用红黑树实现的TreeMap添加、删除和搜索的平均复杂度是O(logn)，其特点是key必须具备可比较性且元素分布是顺序的。
但在实际应用中，很多时候存储的元素不具有可比性，key也不需要具备可比性。

1.1 存储方式

根据传入的key计算出相应的hash值作为数组的索引。

添加、搜索删除的流程都是O(1)。

哈希表内部的数组元素，有时也被称为Bucket（桶），整个数组叫Buckets。

1.2 哈希值 1.2.1 哈希冲突（Hash Collision）及解决方案

也称为哈希碰撞，是两个不同的key，经过哈希值函数计算出相同的结果。

1. 开放定址法（Open Addressing）：按照一定的规则向其它地址探测，直到遇到空桶。
2. 再哈希法（Re-Hashing）：设计多个哈希函数。
3. 链地址法（Seprarte Chaining）：通过链表将同一index的元素串起来。

1.2.2 JDK1.8 解决方案

JDK1.8 使用 链表 + 红黑树 解决哈希冲突。

使用单向链表将元素穿起来；

当元素的值超过一定范围，会由单向链表转为红黑树来存储。
默认范围：哈希表容量（桶数量） ≥ 64，单向链表节点数量大于 8 。

但是当元素数量又少到一定程度时，又会转为单向链表。

1.2.3 哈希函数作用

1. 先生成key对应的整数哈希值；
2. 使用生成的哈希值与数组的大小进行相关运算，生成一个索引值；

根据数组大小计算索引值时，如果使用%运算，会导致概率会很低。这里可以使用&运算，但是需要保证数组的长度为 2ⁿ 次方。
与运算：1001010 & 1101101 = 1001000，即都是1返回1，否则是0。
例如：表的长度 len = 2⁵ = 100000；len - 1 = 011111；新加入的元素的hash值为：1010101 ；1010101 & 0011111 = 0010101
和一个全是1的二进制数进行与运算结果必然小于表的长度。

1.2.4 基本数据类型和字符串的哈希值

1. Int：值直接当作哈希值；

2. Float：将存储的二进制格式转为整数值；

   int bits = floatToIntBits(floatNum);
   

3. Long：因为long的长度为64，而哈希值类型int为32，因此需要进行转换：

   (int) (value ^ (value >>> 32));
   

   计算方式：实际上就是让高 32 bit 与 低 32 bit 进行异或运算：
   

4. Double：需要先转为long类型，剩余和long处理相同。

   long bits = doubleToLongBits(value);
   

5. 字符串：本质上字符串是由字符组成，而字符的本质又是一个整数，这就可以使用字符的位数乘以一个数相加的结果。
   例如：jack = j * n^3^ + j *n^2^ +... + j *n 等价于[ ( j * n + a) * n + c] * n + k。
   在JDK中n取31，因为31是奇素数，31 * i可以优化成：(i << 5) - i。

上方计算方法与JDK的实现方式相同。

1.2.5 自定义对象的哈希值

对象的默认哈希值根据对象的内存地址计算出来的。

重写hashCode()方法：计算出所有属性的哈希值，最后再也字符串的方式将所有的哈希值计算出一个全新的哈希值。

@Data
@AllArgsConstructor
@NoArgsConstructor
public class Person {

    private int age;

    private String name;

    private float weight;

    @Override
    public int hashCode(){
        int hashCode = age;
        hashCode = hashCode * 31 + Float.floatToIntBits(weight);
        hashCode = hashCode * 31 + (name != null ? name.hashCode() : 0);
        return hashCode;
    }
}

1.3 equals()

在hash冲突时（计算出的索引相同），拿到已经存在的key与新的key进行比较，相等就覆盖，不相等就添加到链表最后。该方法就是用来比较key与已经存在的key是否相等。

    
    @Override
    public boolean equals(Object o) {
        // 如果当前对象和传入的对象内存地址一样，一定是一个对象。
        if (this == o){
            return true;
        }
        // 如果传入的对象为空，获取类型不同，一定不是同一个对象。
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        // 比较成员变量是否全部相等
        Person person = (Person) o;
        return age == person.age
                && Float.compare(person.weight, weight) == 0
                && Objects.equals(name, person.name);
    }

1.4 代码实现

这里直接使用数组+红黑树实现。 将红黑树的根节点存放到数组中。

1.4.1 节点设计

存储 k - v 形式的红黑树节点

private static class Node {
        int hash;
        K key;
        V value;
        boolean color = RED;
        Node left;
        Node right;
        Node parent;
        public Node(K key, V value, Node parent) {
            this.key = key;
            int hash = key == null ? 0 : key.hashCode();
            // 根据运算得到哈希值
            this.hash = hash ^ (hash >>> 16);
            this.value = value;
            this.parent = parent;
        }

        public boolean isLeaf() {
            return left == null && right == null;
        }

        public boolean hasTwoChildren() {
            return left != null && right != null;
        }

        public boolean isLeftChild() {
            return parent != null && this == parent.left;
        }

        public boolean isRightChild() {
            return parent != null && this == parent.right;
        }

        public Node sibling() {
            if (isLeftChild()) {
                return parent.right;
            }

            if (isRightChild()) {
                return parent.left;
            }
            return null;
        }
    }

1.4.2 成员变量

	// 红黑树节点颜色
    private static final boolean RED = false;
    private static final boolean BLACK = true;

    // 默认长度为 2 的 4 次方
    private static final int DEFAULT_CAPACITY = 1 << 4;
	
	
    // 哈希表长度
    private int size;

    // 哈希数组（存放红黑树的根节点）
    private Node[] table;

1.4.3 简单方法实现

    public HashMap(){
        table = new Node[DEFAULT_CAPACITY];
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void clear() {
        if (size == 0){
            return;
        }
        // 清空table
        Arrays.fill(table, null);
        size = 0;
    }

1.4.4 添加

• 计算索引：

   
  private int index(K k){
      return hash(k) & (table.length - 1);
  }
  
  
  private int hash(K k){
      // 如果传入的 k 为空，返回 0
      if (k == null){
          return 0;
      }
      int hash = k.hashCode();
      return hash  ^ (hash >>> 16);
  }
  
  
  private int index(Node node){
      return (node.hash) & (table.length - 1);
  }
  

• 查找节点：

	
    private Node node(K k){
        Node root = table[index(k)];
        return root == null ? null : node(root,k);
    }

    
    private Node node(Node node,K k){
        // 获取扰动计算的哈希值
        int newHash = hash(k);
        Node resultNode = null;
        int cmp = 0;
        while (node != null){
            K oldK = node.key;
            int oldHash = node.hash;
            if (newHash > oldHash){ // 新节点哈希值大 - 往右找
                node = node.right;
            }else if (oldHash > newHash){ // 新节点哈希值小 - 往左找
                node = node.left;
            }else if(Objects.equals(k,oldK)){ // 哈希相等，equals，直接返回
                return node;
            }else if (oldK != null && k != null // 都不为空，且一种类型，具备可比较性，并且结果不为0
                    && oldK.getClass() == k.getClass()
                    && k instanceof Comparable
                    && (cmp = ((Comparable) k).compareTo(oldK)) != 0) {
                node = cmp > 0 ? node.right : node.left;
            }else if (node.right != null  // 哈希相等，不具可比较性，不equals 扫描左右子树，并且返回的节点不为空
                    && (resultNode = (node(node.right,k))) != null){
                return resultNode;
            }else {
                node = node.left;
            }
        }
        return null;
    }

• 添加：这里的添加就是，比较比较再比较，然后根据计算出的索引，如果相同就存放到根节点红黑树中。

  public V put(K k, V v)  {
          int index = index(k);
          // 判断索引位置是否有元素
          Node root = table[index];
          if (root == null){ // 没有元素，添加到索引位置，并作为红黑树的根节点
              root = new Node<>(k,v,null);
              table[index] = root;
              size ++;
              // 修复红黑树性质
              afterPut(root);
              return null;
          }
          // 添加的不是第一个节点
          // 找到父节点
          Node parent = root;
          Node node = root;
          int cmp = 0;
          int newHash = hash(k);
          // 存放扫描结果
          Node result = null;
          // 判断是否已经扫描过了
          boolean searched = false;
          do {
              parent = node;
              // 当前索引的 k 和 hash
              K oldK = node.key;
              int oldHash = node.hash;
              if (newHash > oldHash){
                  cmp = 1;
              }else if (newHash < oldHash){
                  cmp = -1;
              }else if (Objects.equals(k,oldK)){ // 哈希值相同且equals直接覆盖
                  cmp = 0;
              }else if (k != null && oldK != null // 可以比较并且比较值不为0
                      && k.getClass() == oldK.getClass()
                      && k instanceof Comparable
                      && (cmp = ((Comparable) k).compareTo(oldK)) != 0){
  
              }else if (searched){ // 已经扫描过了，没有相同的k，直接内存地址相减。
                  cmp = System.identityHashCode(k) - System.identityHashCode(oldK);
              }else {
                  // 扫描左右判断，已经存在就覆盖。
                  if ((node.left != null && (result = node(node.left,k)) != null)
                          || (node.left != null && (result = node(node.left,k)) != null)){
                      node = result;
                      cmp = 0;
                  }else { // 不存在 k
                      searched = true;
                      cmp = System.identityHashCode(k) - System.identityHashCode(oldK);
                  }            
           	}
              if (cmp > 0) {
                  node = node.right;
              } else if (cmp < 0) {
                  node = node.left;
              } else { // 相等就把k 和 v 一块覆盖掉
                  node.key = k;
                  V oldValue = node.value;
                  node.value = v;
                  return oldValue;
              }
          } while (node != null);
          // 插入到父节点的哪个位置
          Node newNode = new Node<>(k, v, parent);
          if (cmp > 0) {
              parent.right = newNode;
          } else {
              parent.left = newNode;
          }
          size++;
          // 新添加节点之后的处理
          afterPut(newNode);
          return null;
      }
  

1.4.5 get() 和 containsKey()

	public V get(K k) {
        Node node = node(k);
        return node == null ? null : node.value;
    }

    public boolean containsKey(K k) {
        return get(k) != null;
    }

1.4.6 remove()

 	public V remove(K k) {
        return remove(node(k));
    }

   private V remove(Node node){

        if (node == null){
            return null;
        }
        size--;

        V oldValue = node.value;

        // 判断度为2
        if (node.hasTwoChildren()){
            // 获取后继节点
            Node s = successor(node);
            // 后继节点的值覆盖当前节点的值
            node.key = s.key;
            node.value = s.value;
            node.hash = s.hash;
            // 将node指向s节点
            node = s;
        }

        // 获取被删除节点的子节点，如果左子节点为空则获取右子节点；
        // 如果子节点都为空，则表示该节点是叶子节点返回null。
        Node relacement = node.left != null ? node.left : node.right;

        // 当前索引中的根节点
        int index = index(node);
        if (relacement != null){ // node 是度为1的节点
            // 更改parent
            relacement.parent = node.parent;
            // 更改parent的left（right）的指向
            if (node.parent == null){ // node是度为1的根节点。
                table[index] = relacement;
            }else if (node == node.parent.left){ // 被删除节点是父节点的左子节点
                node.parent.left = relacement;
            } else { // 被删除节点是父节点的右子节点
                node.parent.right = relacement;
            }
            // 删除之后处理
            afterRemove(relacement);
        }else if(node.parent == null){ // node是叶子节点并且是根节点
            table[index] = null;
            // 删除之后处理
            afterRemove(node);
        }else { //node 是普通叶子节点
            if (node == node.parent.left){ // 当前节点是父节点的右子节点
                node.parent.left = null;
            }else { // 是父节点的左子节点
                node.parent.right = null;
            }

            // 删除之后处理
            afterRemove(node);
        }
        return oldValue;
    }

1.4.6 containsValue()

	public boolean containsValue(V v) {
        if (size == 0){
            return false;
        }
        Queue> queue = new LinkedList();
        for (Node kvNode : table) {
            if (kvNode == null) {
                continue;
            }
            queue.offer(kvNode);
            while (!queue.isEmpty()) {
                Node node = queue.poll();
                if (Objects.equals(v, node.value)) {
                    return true;
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return false;
    }

1.4.8 traversal()

	public void traversal(Visitor visitor) {
        if (size == 0 || visitor == null){
            return;
        }
        Queue> queue = new LinkedList();
        for (Node kvNode : table) {
            if (kvNode == null) {
                continue;
            }
            queue.offer(kvNode);
            while (!queue.isEmpty()) {
                Node node = queue.poll();
                if (visitor.visit(node.key,node.value)){
                    return;
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
    }

1.4.9 扩容

装填因子： 节点总数量 / 哈希表通数组长度，也叫负载因子。在JDK1.8中，如果装填因子超过0.75，就扩容为原来的两倍。

• 新增装填因子全局变量：

	// 装填因子
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

• 移动节点方法

 	 
    private void moveNode(Node newNode){
        // 重置node
        newNode.parent = null;
        newNode.right = null;
        newNode.left = null;
        newNode.color = RED;

        int index = index(newNode.key);
        // 判断索引位置是否有元素
        Node root = table[index];
        if (root == null){ // 空桶
            root = new Node<>(newNode.key,newNode.value,null);
            table[index] = root;
            // 修复红黑树性质
            afterPut(root);
            return;
        }
        // 添加的不是第一个节点
        Node parent = root;
        Node node = root;
        int cmp = 0;
        K newK = newNode.key;
        int newHash = newNode.hash;
        do {
            parent = node;
            // 当前索引的 k 和 hash
            K oldK = node.key;
            int oldHash = node.hash;
            if (newHash > oldHash){
                cmp = 1;
            }else if (newHash < oldHash){
                cmp = -1;
            }else if (newK != null && oldK != null // 可以比较并且比较值不为0
                    && newK.getClass() == oldK.getClass()
                    && newK instanceof Comparable
                    && (cmp = ((Comparable) newK).compareTo(oldK)) != 0){
            }else {
                cmp = System.identityHashCode(newK) - System.identityHashCode(oldK);
            }
            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            }
        } while (node != null);

        if (cmp > 0) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }
        newNode.parent = parent;
        afterPut(newNode);
    }

• 扩容

	 
    private void resize(){
        // 装填因子不足够扩容
        if ((size / table.length) <= DEFAULT_LOAD_FACTOR){
            return;
        }
        Node[] oldTable = this.table;
        // 容量阔为原先的两倍
        this.table = new Node[this.table.length << 1];
        // 扩容之后，原先的索要么不变，要么变为index + 旧容；
        Queue> queue = new LinkedList();
        for (Node kvNode : oldTable) {
            if (kvNode == null) {
                continue;
            }
            queue.offer(kvNode);
            while (!queue.isEmpty()) {
                Node node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                // 移动节点
                moveNode(node);
            }
        }
    }

• 在put开始中调用即可

2. LinkedHashMap

在HashMap的基础上维护元素的添加顺序，使得遍历的结果是遵从添加顺序的。

2.1 构建节点类

如果想要维护元素的添加顺序，使用维护一个双向的指针是最好的选择。

• 创建first和last全局变量：因为链表无论如何存储都需要一个头尾节点。

	// 头节点和尾节点
    private LinkedNode first;
    private LinkedNode last;

• 创建节点类

  	private static class LinkedNode extends Node{
          LinkedNode prev;
          LinkedNode next;
          public LinkedNode(K key, V value, Node parent) {
              super(key, value, parent);
          }
      }
  

• HashMap新增createNode()接口：因为HashMap中的红黑树保存的是Node节点，无法在LinkedHashMap中使用，添加一个创建节点的方法由子类去实现，可以达到添加子类节点的目的。

      
      protected Node createNode(K key, V value, Node parent){
          return new Node<>(key,value,parent);
      }
  

• 修改HashMap.put()方法中创建节点，使用createNode()实现。

• LinkedHashMap实现方法：

 	@Override
    protected Node createNode(K key, V value, Node parent) {
        LinkedNode node = new LinkedNode<>(key, value, parent);
        if (first == null){  // 头节点为空时
            first = last = node;
        }else { // 新元素作为最后一个元素
            last.next = node;
            node.prev = last;
            last = node;
        }
        return node;
    }

2.2 修改方法

• clear()：在父类的基础上，将first和last赋值为空。

    public void clear() {
        super.clear();
        first = null;
        last = null;
    }

• traversal()：以链表的方式遍历。

	public void traversal(Visitor visitor) {
        if (visitor == null){
            return;
        }
        LinkedNode node = this.first;
        while (node != null){
            if (visitor.visit(node.key,node.value)){
                return;
            }
            node = node.next;
        }
    }

• remove()：在父类针对红黑树删除的基础上，删除掉链表之间的线。但是再删除度为2的节点时，会由该节点的后继节点来代替该节点，但此时修改链表指向的节点是替换的节点而不是删除的节点，如下图：

  删除之前：… 52 -> 37 -> 21 -> 31 -> 41
  
  删除31之后：… 52 -> 21 -> 37 -> 41
  
  导致21变成了37的前驱节点。发生错误。
  新增方法修复链表：
  父类新增：

  	    
  	    protected void afterRemoveLinked(Node willNode,Node node){
  	
  	    }
  

  子类实现：

      @Override
      protected void afterRemoveLinked(Node willNode, Node node) {
          LinkedNode linkedWillNode = (LinkedNode) willNode;
          LinkedNode linkedNode = (LinkedNode) node;
  
          if (linkedWillNode != linkedNode) {
              // 交换linkedWillNode和linkedRemovedNode在链表中的位置
              // 交换prev
              LinkedNode tmp = linkedWillNode.prev;
              linkedWillNode.prev = linkedNode.prev;
              linkedNode.prev = tmp;
              if (linkedWillNode.prev == null) {
                  first = linkedWillNode;
              } else {
                  linkedWillNode.prev.next = linkedWillNode;
              }
              if (linkedNode.prev == null) {
                  first = linkedNode;
              } else {
                  linkedNode.prev.next = linkedNode;
              }
  
              // 交换next
              tmp = linkedWillNode.next;
              linkedWillNode.next = linkedNode.next;
              linkedNode.next = tmp;
              if (linkedWillNode.next == null) {
                  last = linkedWillNode;
              } else {
                  linkedWillNode.next.prev = linkedWillNode;
              }
              if (linkedNode.next == null) {
                  last = linkedNode;
              } else {
                  linkedNode.next.prev = linkedNode;
              }
          }
  
          LinkedNode prev = linkedNode.prev;
          LinkedNode next = linkedNode.next;
          if (prev == null){
              first = next;
          }else {
              prev.next = next;
          }
          if (next == null){
              last = prev;
          }else {
              next.prev = prev;
          }
      }
  
  

  修改父类remove(Node node):

      
      protected V remove(Node node){
  
          Node willNode = node;
  
          if (node == null){
              return null;
          }
          size--;
  
          V oldValue = node.value;
  
          // 判断度为2
          if (node.hasTwoChildren()){
              // 获取后继节点
              Node s = successor(node);
              // 后继节点的值覆盖当前节点的值
              node.key = s.key;
              node.value = s.value;
              node.hash = s.hash;
              // 将node指向s节点
              node = s;
          }
  
          // 获取被删除节点的子节点，如果左子节点为空则获取右子节点；
          // 如果子节点都为空，则表示该节点是叶子节点返回null。
          Node relacement = node.left != null ? node.left : node.right;
  
          // 当前索引中的根节点
          int index = index(node);
          if (relacement != null){ // node 是度为1的节点
              // 更改parent
              relacement.parent = node.parent;
              // 更改parent的left（right）的指向
              if (node.parent == null){ // node是度为1的根节点。
                  table[index] = relacement;
              }else if (node == node.parent.left){ // 被删除节点是父节点的左子节点
                  node.parent.left = relacement;
              } else { // 被删除节点是父节点的右子节点
                  node.parent.right = relacement;
              }
              // 删除之后处理
              afterRemove(relacement);
          }else if(node.parent == null){ // node是叶子节点并且是根节点
              table[index] = null;
              // 删除之后处理
              afterRemove(node);
          }else { //node 是普通叶子节点
              if (node == node.parent.left){ // 当前节点是父节点的右子节点
                  node.parent.left = null;
              }else { // 是父节点的左子节点
                  node.parent.right = null;
              }
              // 删除之后处理
              afterRemove(node);
          }
          afterRemoveLinked(willNode, node);
          return oldValue;
      }
  

3. HashSet和LinkedHashSet

利用哈希表实现set

3.1 HashSet

public class HashSet implements Set {

    private HashMap map = new HashMap<>();

    @Override
    public int size() {
        return map.size();
    }

    @Override
    public boolean isEmpty() {
        return map.isEmpty();
    }

    @Override
    public void clear() {
        map.clear();
    }

    @Override
    public boolean contains(E e) {
        return map.containsKey(e);
    }

    @Override
    public void add(E e) {
        map.put(e,null);
    }

    @Override
    public void remove(E e) {
        map.remove(e);
    }

    @Override
    public void traversal(Visitor visitor) {
        map.traversal(new Map.Visitor() {
            @Override
            public boolean visit(E e, Object o) {
                return visitor.visit(e);
            }
        });
    }
}

3.2 LinkedHashSet

public class LinkedHashSet implements Set {

    private LinkedHashMap map = new LinkedHashMap<>();

    @Override
    public int size() {
        return map.size();
    }

    @Override
    public boolean isEmpty() {
        return map.isEmpty();
    }

    @Override
    public void clear() {
        map.clear();
    }

    @Override
    public boolean contains(E e) {
        return map.containsKey(e);
    }

    @Override
    public void add(E e) {
        map.put(e,null);
    }

    @Override
    public void remove(E e) {
        map.remove(e);
    }

    @Override
    public void traversal(Visitor visitor) {
        map.traversal(new Map.Visitor() {
            @Override
            public boolean visit(E e, Object o) {
                return visitor.visit(e);
            }
        });
    }
}