欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

基于散列实现的HashMap

程序员文章站 2022-03-15 19:36:32
...
public class SimpleHashMap<K, V> {
    static final int SIZE = 997;
    static class MapEntry<K, V> implements Map.Entry<K, V> {

        private final K key;
        private V value;    
        public MapEntry(K key, V value) {
            this.key = key;
            this.value = value;
        }
        @Override
        public K getKey() {
            return key;
        }
        @Override
        public V getValue() {
            return value;
        }
        @Override
        public V setValue(V value) {
            this.value = value;
            return value;
        }   
    }
    @SuppressWarnings("unchecked")
    LinkedList<MapEntry<K, V>>[] buckets = new LinkedList[SIZE];
    private int size;

    public void put(K key, V value) {
        int index = hashIndexOf(key);
        if(buckets[index] == null)
            buckets[index] = new LinkedList<>();
        LinkedList<MapEntry<K, V>> bucket = buckets[index];
        if(findEntry(bucket.listIterator(), key) == null) {
            bucket.add(new MapEntry<K, V>(key, value));
            size ++;
        }
        
    }

    private int hashIndexOf(K key) {
        Objects.requireNonNull(key);
        return Math.abs(key.hashCode()) % SIZE;
    }

    private MapEntry<K, V> findEntry(Iterator<MapEntry<K, V>> iterator, K key) {
        while(iterator.hasNext()) {
            MapEntry<K, V> oldMapEntry = iterator.next();
            if(oldMapEntry.getKey().equals(key)) {
                return oldMapEntry;
            }
        }
        return null;
    }

    public V get(K key) {
        ListIterator<MapEntry<K, V>> iterator = buckets[hashIndexOf(key)].listIterator();
        return findEntry(iterator, key).getValue();
    }

    public int size() {
        return size;
    }
}