[数据结构与算法]数组链表模拟、HashSet扩容机制

数组链表模拟

• HashSet底层机制说明

• HashSet的底层是HashMap，HashMap的底层是(数组+链表+红黑树)

import java.util.Arrays;
?
public class HashSetStructure {
 ? ?public static void main(String[] args) {
 ? ? ? ?//创建数组
 ? ? ? ?Node[] node = new Node[16];
 ? ? ? ?
 ? ? ? ?Node jack = new Node("Jack", null);
 ? ? ? ?node[2] = jack; ?//数组索引2位置插入数据
 ? ? ? ?Node tom = new Node("Tom", null);
 ? ? ? ?jack.next = tom; ?//创建链表,数组索引2位置数据指定链表下一个为Tom
 ? ? ? ?Node cici = new Node("CiCi",null);
 ? ? ? ?tom.next = cici; ?//指定链表Tom下一个数据为CiCi
?
 ? ? ? ?Node rose = new Node("Rose", null);
 ? ? ? ?node[3] = rose; ?//数组索引3位置插入数据
?
 ? ? ? ?//输出数组
 ? ? ? ?System.out.println(Arrays.toString(node));
 ?  }
}
class Node{
 ? ?Object item; // 存放数据
 ? ?Node next; ?//指向下一个节点
?
 ? ?public Node(Object item, Node next) {
 ? ? ? ?this.item = item;
 ? ? ? ?this.next = next;
 ?  }
}
/*
[null, null, com.yu.Collections.Set.Node@1b6d3586, com.yu.Collections.Set.Node@4554617c, null, null, null, null, null, null, null, null, null, null, null, null]
 */

HashSet扩容机制

• HashSet底层是HashMap

• 添加一个元素时，先得到hash值 -- > 会转换程 --> 索引值

• 找到存储数据表Node，看这个索引位置是否已经存放的有元素

• 如果没有，直接加入

• 如果有，调用equals比较，如果相同，就放弃添加，如果不相同，则添加到最后

• 在Java8中，如果一条联保的元素个数超过TREEIFY_THRESHOLD(默认是8)，并且table的大小>=MIN_TREEIFY_CAPACITY(默认64)，就会进行树化(红黑树)