CS61B spring21 lab7代码

MyHashMap.java

package hashmap;

import jdk.nashorn.internal.ir.ReturnNode;

import javax.security.auth.kerberos.KerberosKey;
import java.nio.channels.SelectableChannel;
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> {

    private double factor;

    @Override
    public void clear() {
        buckets = (Collection<Node>[])new Collection[initialSize];
        for (int i = 0; i < initialSize; i++) {
            buckets[i] = createBucket();   //
        }
        this.size = 0;
    }

    @Override
    public boolean containsKey(K key) {
        Node node = find(key);
        if (node != null) {
            return true;
        }
        return false;
    }

    @Override
    public V get(K key) {       //如果找到了
        Node node = find(key);
        if (node != null) {
            return node.value;
        }
        return null;
    }

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

    @Override
    public void put(K key, V value) {
        int hashcode = hashcode(key);
        Collection<Node> bucket = buckets[hashcode];

        for (Node node : bucket) {
            if (node.key == key) {
                bucket.remove(node);
                Node node1 = node;
                node1.value = value;
                bucket.add(node1);
                return;
            }
        }
        bucket.add(createNode(key,value));      //
        this.size += 1;     //如果是相同的就不用增加size
    }
    public Node find(K key) {
        int hashcode = hashcode(key);          // 使用
        Collection<Node> bucket = buckets[hashcode];
        for (Node node : bucket) {
            if (node.key.equals(key)) {
                return node;    //如果找到了就返回node
            }
        }
        return null;
    }

    private int hashcode(K key) {
        return key == null  ?  0 : (key.hashCode() & 0x7fffffff) % initialSize;       //作为哈希函数
    }

    @Override
    public Set<K> keySet() {
        Set<K> objects = new HashSet<>();
        for (Collection<Node> bucket : buckets) {
            for (Node node : bucket) {      //为什么会找不到呢
                objects.add(node.key);
            }
        }

        return objects;
    }

    @Override
    public V remove(K key) {

        return null;
    }

    @Override
    public V remove(K key, V value) {
        return null;
    }

    @Override
    public Iterator<K> iterator() {
        return null;
    }

    /**
     * Protected helper class to store key/value pairs
     * The protected qualifier allows subclass access
     */
    protected class Node {
        K key;
        V value;

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

    /* Instance Variables */
    private int size;
    private Collection<Node>[] buckets;    //buckets
    private int initialSize = 16;
    private double loadFactor = 0.75;
    // You should probably define some more!

    /** 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) {     //使用
        buckets = (Collection<Node>[])new Collection[initialSize];
        for (int i = 0; i < initialSize; i++) {
            buckets[i] = createBucket();   //
        }
        this.factor = maxLoad;
    }

    /**
     * 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 LinkedList<Node>();      //返回这样的一个东西
    }

    /**
     * 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 null;
    }

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

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202

可以通过所有测试