收获点

本次Lab主要介绍了工厂化代码的思想

启动文件的继承结构如下：

Map61B.java
└── MyHashMap.java
    ├── MyHashMapALBuckets.java
    ├── MyHashMapHSBuckets.java
    ├── MyHashMapLLBuckets.java
    ├── MyHashMapPQBuckets.java
    └── MyHashMapTSBuckets.java

在这个哈希表中，有一个工厂方法 createBucket() 和 createTable(int tableSize)。

createBucket() 方法用于创建一个存储 Node 的桶。在下面的实现中，使用 LinkedList 作为桶的数据结构，因此这个工厂方法返回了一个 LinkedList<Node>。你可以通过重写这个方法来选择其他数据结构作为桶的实现。
createTable(int tableSize) 方法用于创建底层数组，即哈希表的主要存储结构。这个方法会创建一个长度为 tableSize 的数组，然后遍历数组，为每个位置创建一个桶，调用 createBucket() 方法创建桶对象。最后返回创建好的数组，作为哈希表的底层存储结构。这个方法允许你灵活地选择数组的长度，以及每个桶的具体实现方式。

在 MyHashMap 的构造函数中，通过调用 createTable(capacity) 方法来初始化 buckets，这样就创建了一个指定容量的哈希表。在哈希表的 resize(int newCapacity) 方法中，同样会使用 createTable(newCapacity) 来创建新的更大容量的哈希表，并将原有的键值对重新哈希到新的数组中。

这种工厂方法的设计允许了灵活性和可扩展性，可以方便地修改和替换哈希表的内部数据结构，以满足不同的需求和性能要求。

哈希表API

package hashmap;

import java.util.Set;
/**
 * Your implementation hashmap.MyHashMap should implement this interface. To do so,
 * append "implements hashmap.Map61B<K, V>" to the end of your "public class..."
 * declaration, though you can use other formal type parameters if you'd like.
 */
public interface Map61B<K, V> extends Iterable<K> {
    /** Removes all of the mappings from this map. */
    void clear();

    /** Returns true if this map contains a mapping for the specified key. */
    boolean containsKey(K key);

    /**
     * Returns the value to which the specified key is mapped, or null if this
     * map contains no mapping for the key.
     */
    V get(K key);

    /** Returns the number of key-value mappings in this map. */
    int size();

    /**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key,
     * the old value is replaced.
     */
    void put(K key, V value);

    /** Returns a Set view of the keys contained in this map. */
    Set<K> keySet();

    /**
     * Removes the mapping for the specified key from this map if present.
     * Not required for Lab 8. If you don't implement this, throw an
     * UnsupportedOperationException.
     */
    V remove(K key);

    /**
     * Removes the entry for the specified key only if it is currently mapped to
     * the specified value. Not required for Lab 8. If you don't implement this,
     * throw an UnsupportedOperationException.
     */
    V remove(K key, V value);
}

代码实现

package hashmap;

import java.util.*;

/**
 *  A hash table-backed Map implementation. Provides amortized constant time
 *  access to elements via get(), remove(), and put() in the best case.
 *
 *  Assumes null keys will never be inserted, and does not resize down upon remove().
 *  @author YOUR NAME HERE
 */
public class MyHashMap<K, V> implements Map61B<K, V> {

    protected class Node {
        K key;
        V value;

        Node(K k, V v) {
            key = k;
            value = v;
        }
    }

    /* Instance Variables */
    private Collection<Node>[] buckets;
    // You should probably define some more!

    private int size;

    private double loadFactor;
    private int capacity;

    /** Constructors */
    public MyHashMap() {
        this(16, 0.75);
    }

    public MyHashMap(int initialSize) {
        this(initialSize, 0.75);
    }

    /**
     * MyHashMap constructor that creates a backing array of initialSize.
     * The load factor (# items / # buckets) should always be <= loadFactor
     *
     * @param initialSize initial size of backing array
     * @param maxLoad maximum load factor
     */
    public MyHashMap(int initialSize, double maxLoad) {
        capacity = initialSize;
        buckets = createTable(capacity);
        loadFactor = maxLoad;
        size = 0;
    }

    /**
     * Returns a new node to be placed in a hash table bucket
     */
    private Node createNode(K key, V value) {
        return new Node(key, value);
    }

    /**
     * Returns a data structure to be a hash table bucket
     *
     * The only requirements of a hash table bucket are that we can:
     *  1. Insert items (`add` method)
     *  2. Remove items (`remove` method)
     *  3. Iterate through items (`iterator` method)
     *
     * Each of these methods is supported by java.util.Collection,
     * Most data structures in Java inherit from Collection, so we
     * can use almost any data structure as our buckets.
     *
     * Override this method to use different data structures as
     * the underlying bucket type
     *
     * BE SURE TO CALL THIS FACTORY METHOD INSTEAD OF CREATING YOUR
     * OWN BUCKET DATA STRUCTURES WITH THE NEW OPERATOR!
     */
    protected Collection<Node> createBucket() {
        return new ArrayList<>();
    }

    /**
     * Returns a table to back our hash table. As per the comment
     * above, this table can be an array of Collection objects
     *
     * BE SURE TO CALL THIS FACTORY METHOD WHEN CREATING A TABLE SO
     * THAT ALL BUCKET TYPES ARE OF JAVA.UTIL.COLLECTION
     *
     * @param tableSize the size of the table to create
     */
    private Collection<Node>[] createTable(int tableSize) {
        return (Collection<Node>[]) new Collection[tableSize];
    }

    // TODO: Implement the methods of the Map61B Interface below
    // Your code won't compile until you do so!

    /**
     * Removes all of the mappings from this map.
     */
    @Override
    public void clear() {
        MyHashMap<K, V> newTable = new MyHashMap<>();
        size = newTable.size();
        capacity = newTable.capacity;
        loadFactor = newTable.loadFactor;
        buckets = newTable.buckets;
    }

    /**
     * Returns true if this map contains a mapping for the specified key.
     *
     * @param key
     */
    @Override
    public boolean containsKey(K key) {
        if (key == null) {
            throw new IllegalArgumentException("key is null in containsKey() function");
        }
        return get(key) != null;
    }

    /**
     * Returns the value to which the specified key is mapped, or null if this
     * map contains no mapping for the key.
     *
     * @param key
     */
    @Override
    public V get(K key) {
        if (key == null) {
            throw new IllegalArgumentException("the key is null in get() function");
        }
        Collection<Node> bucket = getBucket(key);
        if (bucket != null) {
            for (Node node : bucket) {
                if (node.key.equals(key)) {
                    return node.value;
                }
            }
        }
        return null;
    }

    /**
     * Returns the number of key-value mappings in this map.
     */
    private int hashCode(K num) {
        return Math.abs(num.hashCode()) % capacity;
    }
    private Collection<Node> getBucket(K k) {
        int index = hashCode(k);
        return buckets[index];
    }
    @Override
    public int size() {
        return size;
    }

    /**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key,
     * the old value is replaced.
     *
     * @param key
     * @param value
     */
    @Override
    public void put(K key, V value) {
        Collection<Node> bucket = getBucket(key);
        if (bucket == null) {
            // if bucket dont exist
            int index = hashCode(key);
            buckets[index] = createBucket();
            bucket = buckets[index];
        }
        putIn(bucket, key, value);
        double load = (double) size() /capacity;
        if (load > loadFactor) {
            resize(2 * capacity);
        }
    }

    private void resize(int size) {
        capacity = size;
        Collection<Node>[] newBuckets = createTable(size);
        for (Collection<Node> bucket : buckets) {
            if (bucket != null) {
                for (Node node : bucket) {
                    int index = hashCode(node.key);
                    if (newBuckets[index] == null) {
                        newBuckets[index] = createBucket();
                    }
                    newBuckets[index].add(node);
                }
            }
        }
        buckets = newBuckets;
    }

    private void putIn(Collection<Node> bucket, K key, V value) {
        for (Node x : bucket) { // iterate the bucket
            if (x.key.equals(key)) { // find the exact key
                x.value = value;
                return;
            }
        }
        bucket.add(new Node(key, value));
        size++;
    }
    /**
     * Returns a Set view of the keys contained in this map.
     */
    @Override
    public Set<K> keySet() {
        Set<K> keySet = new HashSet<>();
        for (Collection<Node> bucket : buckets) {
            if (bucket != null) {
                for (Node node : bucket) {
                    keySet.add(node.key);
                }
            }
        }
        return keySet;
    }

    /**
     * Removes the mapping for the specified key from this map if present.
     * Not required for Lab 8. If you don't implement this, throw an
     * UnsupportedOperationException.
     *
     * @param key
     */
    @Override
    public V remove(K key) {
        throw new UnsupportedOperationException();
    }

    /**
     * Removes the entry for the specified key only if it is currently mapped to
     * the specified value. Not required for Lab 8. If you don't implement this,
     * throw an UnsupportedOperationException.
     *
     * @param key
     * @param value
     */
    @Override
    public V remove(K key, V value) {
        throw new UnsupportedOperationException();
    }

    /**
     * Returns an iterator over elements of type {@code T}.
     *
     * @return an Iterator.
     */
    @Override
    public Iterator<K> iterator() {
        return null;
    }

    /**
     * Protected helper class to store key/value pairs
     * The protected qualifier allows subclass access
     */

}