关于java:基于拉链式和线性探测式散列表实现Map

40次阅读

共计 5343 个字符，预计需要花费 14 分钟才能阅读完成。

前言

前几篇咱们一起学习了基于数组、链表、二叉树、红黑树来实现 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 值

@Override
public int hashCode() {return Integer.hashCode(value);
}
public static int hashCode(int value) {return value;}

Long

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

@Override
public int hashCode() {return Long.hashCode(value);
}

public static int hashCode(long value) {return (int)(value ^ (value >>> 32));
}

Double、Float

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

public static int hashCode(float value) {return floatToIntBits(value);
}
public static int floatToIntBits(float value) {int result = floatToRawIntBits(value);
    // Check for NaN based on values of bit fields, maximum
    // exponent and nonzero significand.
    if (((result & FloatConsts.EXP_BIT_MASK) ==
          FloatConsts.EXP_BIT_MASK) &&
         (result & FloatConsts.SIGNIF_BIT_MASK) != 0)
        result = 0x7fc00000;
    return result;
}

String

java 中每个 char 都能够示意成一个 int 值，所以字符串转换成一个 int 值

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;
}

软缓存

如果计算一个散列值比拟耗时，那么我能够这个计算好的值缓存起来，即应用一个变量把这个值保存起来，在下一次调用时间接返回。Java 中的 String 就是采纳的这种形式。

拉链式的散列表

散列函数可能将键值转换成数组的下标；第二步就是须要解决碰撞抵触，也就是须要解决遇到了两个散列值雷同的对象应该如何存储。有一种形式是数组中的每一个元素都指向一个链表用来寄存散列值雷同的对象，这种形式被称为拉链法

拉链法能够应用原始的链表保留键，也能够采纳咱们之前实现的红黑树来示意，在 java8 中采纳的这两种形式的混合，在节点数超过了 8 之后变为红黑树。

这里咱们就采纳简略的链表来实现拉链式散列表，数据结构应用在前几篇中曾经实现的LinkedMap，能够参考后面的文章《基于数组或链表实现 Map》。

public class SeparateChainingHashMap<K, V> implements Map<K, V> {

    private int size;
    private LinkedMap<K, V>[] table;

    public SeparateChainingHashMap(int capacity) {this.table = (LinkedMap<K, V>[]) new LinkedMap[capacity];
        for (int i = 0; i < capacity; i++) {this.table[i] = new LinkedMap<>();}
    }

    @Override
    public void put(K key, V value) {this.table[hash(key)].put(key, value);
        size++;
    }

    private int hash(K key) {return (key.hashCode() & 0x7fffffff) % table.length;
    }

    @Override
    public V get(K key) {return this.table[hash(key)].get(key);
    }

    @Override
    public void delete(K key) {this.table[hash(key)].delete(key);
        size--;
    }

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

}

这的 hash 函数应用 key 的 hashCode 与上 0x7fffffff 失去一个非负的整数，而后再应用除留余数法计算出数组的下标。其中 0x7FFFFFFF 的二进制示意就是除了首位是 0，其余都是 1，也就是说，这是最大的整型数 int（因为第一位是符号位，0 示意他是负数）, 能够应用 Integer.MAX_VALUE 代替

散列表的次要目标在于把键值平均的散布到数组中，所以散列表是无序的，如果你须要的 Map 须要反对取出最大值，最小值，那么散列表都不适宜。

这里咱们实现的拉链式散列表的数组大小是固定的，然而通常在随着数据量的增大，越短的数组呈现碰撞的几率会增大，所以须要数组反对动静的扩容，扩容之后须要把原来的值从新插入到扩容之后的数组中。数组的扩容能够参考之前的文章《老哥是时候来温习下数据结构与算法了》

线性探测式散列表

实现散列表的另一种形式就是用大小为 M 来保留 N 个键值，其中 M >N；解决碰撞抵触就须要利用数组中的空位；这种形式中最简略的实现就是线性探测。

线性探测的次要思路：当插入一个键，产生碰撞抵触之后间接把索引加一来查看下一个地位，这时候会呈现三种状况:

  1. 下一个地位和待插入的键相等，那么值就批改值
  2. 下一个地位和待插入的键不相等，那么索引加一持续查找
  3. 如果下一个地位还是一个空位，那么间接把待插入对象放入到这个空位

初始化

线性探测式散列表应用两个数组来寄存 keys 和 values，capacity示意初始化数组的大小

private int size;
private int capacity;
private K[] keys;
private V[] values;

public LinearProbingHashMap(int capacity) {
    this.capacity = capacity;
    this.keys = (K[]) new Object[capacity];
    this.values = (V[]) new Object[capacity];
}

插入

  1. 当插入键的地位超过了数组的大小，就须要回到数组的开始地位持续查找，直到找到一个地位为 null 的才完结；index = (index + 1) % capacity
  2. 当数组已寄存的容量超过了数组总容量的一半，就须要扩容到原来的 2 倍
@Override
public void put(K key, V value) {if (Objects.isNull(key)) {throw new IllegalArgumentException("Key can not null");
    }
    if (this.size > this.capacity / 2) {resize(2 * this.capacity);
    }
    int index;
    for (index = hash(key); this.keys[index] != null; index = (index + 1) % capacity) {if (this.keys[index].equals(key)) {this.values[index] = value;
            return;
        }
    }
    this.keys[index] = key;
    this.values[index] = value;
    size++;
}

动静调整数组的大小

咱们能够参考之前在文章《老哥是时候来温习下数据结构与算法了》中实现的动静调整数据的大小；在线性探测中须要把原来的数据从新插入到扩容之后的数据，因为数组的大小变了须要从新计算索引的地位。

private void resize(int cap) {LinearProbingHashMap<K, V> linearProbingHashMap = new LinearProbingHashMap<>(cap);
    for (int i = 0; i < capacity; i++) {linearProbingHashMap.put(keys[i], values[i]);
    }
    this.keys = linearProbingHashMap.keys;
    this.values = linearProbingHashMap.values;
    this.capacity = linearProbingHashMap.capacity;
}

查问

线性探测散列表中实现查问的思路：依据待查问 key 的 hash 函数计算出索引的地位，而后开始判断以后地位上的 key 是否和待查问 key 相等，如果相等那么就间接返回 value，如果不相等那么就持续查找下一个索引直到遇到某个地位是 null 才完结，示意查问的 key 不存在；

@Override
public V get(K key) {if (Objects.isNull(key)) {throw new IllegalArgumentException("Key can not null");
    }
    int index;
    for (index = hash(key); this.keys[index] != null; index = (index + 1) % capacity) {if (this.keys[index].equals(key)) {return this.values[index];
        }
    }
    return null;
}

删除元素

线性探测式的删除略微麻烦一些，首先须要查找出待删除的元素地位，删除元素之后须要把以后索引之后的间断地位上的元素从新插入；因为是否有空位对于线性探测式散列表的查找至关重要；例如：5->7->9，删除了 7 之后，如果不从新插入 7 的地位就是空位，那么 get 办法将无奈查问到 9 这个元素；

每次删除之后都须要检测一次数组中理论元素的个数，如果与数组的容量相差较大，就能够进行缩容操作；

@Override
public void delete(K key) {if (Objects.isNull(key)) {throw new IllegalArgumentException("Key can not null");
    }
    int index;
    for (index = hash(key); this.keys[index] != null; index = (index + 1) % capacity) {if (this.keys[index].equals(key)) {this.keys[index] = null;
            this.values[index] = null;
            break;
        }
    }

    for (index = (index + 1) % capacity; this.keys[index] != null; index = (index + 1) % capacity) {
        this.size--;
        this.put(this.keys[index], this.values[index]);
        this.keys[index] = null;
        this.values[index] = null;
    }
    this.size--;
    if (size > 0 && size < capacity / 4) {resize(capacity / 2);
    }

}

文中所有源码已放入到了 github 仓库:
https://github.com/silently9527/JavaCore

程序员必读书单：https://github.com/silently9527/ProgrammerBooks

微信公众号：贝塔学 Java

最初（点关注，不迷路）

文中或者会存在或多或少的有余、谬误之处，有倡议或者意见也十分欢送大家在评论交换。

最初，写作不易，请不要白嫖我哟 ，心愿敌人们能够 点赞评论关注 三连，因为这些就是我分享的全副能源起源🙏

正文完
java
发表至： java
2021-04-13
 0
关于java:Java中的程序进程线程
关于java:Guava-规避OOM需要注意的点
View之invalidate，requestLayout，postInvalidate
关于java:23种设计模式Java版第五篇