## Java之HashSet的实现 基于java.util.Set接口实现的简单版HashSet。 ~~~ /** * HashSet实现 * @Author: mango * @Date: 2022/5/21 10:48 下午 */ public class HashSet<V> implements Set<V> { private Node<V>[] array; // 容量 private int capacity; // 大小 private int size; // 默认容量 private int DEFAULT_CAPACITY = 8; // 负载因子 private double LOAD_FACTOR = 0.75; @Override public Object[] toArray() { Object[] arr = new Object[size]; int count = 0; for(int i=0;i<capacity;i++){ Node<V> node = array[i]; if(node != null){ arr[count++] = node.val; while (node.next != null){ arr[count++] = node.next.val; node = node.next; } } } return arr; } private void copy(Object[] a, Object[] b){ int count = Math.min(a.length,b.length); for(int i=0;i<count;i++){ b[i] = a[i]; } } @Override public <T> T[] toArray(T[] a) { copy(toArray(),a); return a; } @Override public Iterator<V> iterator() { Object[] arr = toArray(); int size = arr.length; Iterator<V> iterator = new Iterator<V>() { int cursor = 0; @Override public boolean hasNext() { return cursor < size; } @Override public V next() { return (V) arr[cursor++]; } }; return iterator; } @Override public int size() { return 0; } @Override public boolean isEmpty() { return size == 0; } @Override public boolean contains(Object o) { return getNode(hash(o), (V) o) != null ? true : false; } private void resize(){ int m = (int) (capacity * LOAD_FACTOR / 2); // 超过负载，则扩容 if(size / capacity > LOAD_FACTOR){ resize(1); System.out.println("扩容"); } // 低于负载的一半，且缩减后的容量不小于默认容量，则缩容 else if(size < m && m >= (DEFAULT_CAPACITY / 2) ){ resize(0); System.out.println("缩容"); } } // 扩容,缩容 private void resize(int flag){ int oldCapacity = capacity; Node<V>[] oldArray = this.array; if(flag == 1) { this.capacity = this.capacity << 1; }else{ this.capacity = this.capacity >> 1; } this.array = new Node[capacity]; this.size = 0; for(int i=0;i<oldCapacity;i++){ Node<V> node = oldArray[i]; if(node != null){ addVal(node.val); while (node.next != null){ addVal(node.next.val); node = node.next; } } } } private Node<V> getNode(int hash, V val){ int index = hash % capacity; if(array[index] == null){ return null; }else{ Node<V> node = array[index]; while (node != null && !node.val.equals(val)){ node = node.next; } if(node != null){ return node; } } return null; } static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } private void addVal(V val){ int index = hash(val) % capacity; Node<V> node = array[index]; // 如果存在，则跳过 if(contains(val)){ return ; } // 不存在，则加入 if(node == null){ array[index] = new Node(val); }else{ while (node.next != null){ node = node.next; } node.next = new Node(val); } size++; } @Override public boolean add(V v) { // 如果为空，则先创建默认容量大小的数组 if(array == null){ this.array = new Node[DEFAULT_CAPACITY]; this.capacity = DEFAULT_CAPACITY; } // 设置值 addVal(v); // 控制容量 resize(); return true; } @Override public boolean remove(Object o) { if(contains(o)){ int index = hash(o) % capacity; if(array[index] != null){ Node<V> node = array[index]; if(node.next == null){ array[index] = null; }else{ while (node.next != null && !node.next.val.equals(o)){ node = node.next; } node.next = node.next.next; } size--; // 控制容量 resize(); } } return true; } @Override public boolean containsAll(Collection<?> c) { boolean result = true; for(Object o : c){ if(!contains(o)){ result = false; break; } } return result; } @Override public boolean addAll(Collection<? extends V> c) { c.forEach(e-> addVal(e)); return true; } @Override public boolean retainAll(Collection<?> c) { return false; } @Override public boolean removeAll(Collection<?> c) { c.forEach(e-> remove(e)); return true; } @Override public void clear() { this.size = 0; this.capacity = 0; this.array = null; } /** * 链表节点 */ final class Node<V> { public V val; public Node<V> next; public Node(V val) { this.val = val; } @Override public String toString() { return "Node{" + "val=" + val + ", next=" + next + '}'; } } @Override public String toString() { return "HashSet{" + "array=" + Arrays.toString(array) + ", capacity=" + capacity + ", size=" + size + '}'; } } ~~~