手写 HashSet的底层 和 迭代器

  1 package Test.CollectionIterator;

  2 import java.util.Iterator;

  3 public class MyHashSet2<E> implements Iterable<E>{

  4     //1.数组+链表 一个add 方法

  5     private Node[] arr;

  6     private int size;//返回list中的元素个数

  7     public int size() {

  8         return size;

  9     }

 10     public boolean add(E e) {

 11         boolean flag = false;

 12         //1.判断arr数组是否存在 不存在就创建 存在就添加

 13         if (arr == null) {

 14             arr = new Node[16];//1.1不存在 创建

 15         }

 16         //1.2 添加

 17         //2.根据分组的下标判断 数组下标处 有没有node元素

 18         int index = e.hashCode() % 16;

 19         if (arr[index] == null) {

 20             arr[index] = new Node(e, null);//2.1没有直接创建

 21             size++;

 22             flag = true;

 23         } else {//2.2有的话比较

 24             //3.如果hash值和equals值相等 就不添加 否则添加

 25             Node node = arr[index];

 26             E e1 = (E)node.getE();

 27             Node next;

 28             do {//3.1循环判读是否相等相等就不添加

 29                 if (e1.hashCode() == e.hashCode() && e1.equals(e)) {

 30                     return flag;//相等不添加

 31                 }//

 32                 next = node.getNext();

 33                 if (next != null) {

 34                     e1 = (E)next.getE();

 35                 }

 36             } while (next != null);//这步是比较完数组某个链表上的全部元素

 37             //3.2不相等 开始添加

 38             arr[index] = new Node(e, node);//2.1没有直接创建

 39             size++;

 40             flag = true;

 41         }

 42         return flag;

 43     }

 44     @Override

 45     public Iterator<E> iterator() {

 46         return new Itr();

 47     }

 48     private class Itr<E> implements Iterator{

 49         private int curser;//记录 节点数组 的下标

 50         private  int count;

 51         private Node currentNode;

 52

 53         @Override

 54         public boolean hasNext() {

 55             return count!=size;

 56         }

 57

 58         @Override

 59         public E next() {

 60             if (count>=size){

 61                 throw  new RuntimeException("没有找到下一个");

 62             }

 63           currentNode=arr[curser];

 64             if(currentNode==null){

 65                 while (true){

 66                     curser++;

 67                     if(curser>16)throw  new RuntimeException("没有找到下一个");

 68                     currentNode=arr[curser];

 69                     if(currentNode==null){

 70                         curser++;

 71                     }else {

 72                         count++;

 73                         return (E) currentNode.getE();

 74                     }

 75                 }

 76             }else{

 77                 count++;

 78                 Node now =currentNode;

 79                 if (currentNode.getNext()==null){

 80                    curser++;

 81                 }else {

 82                     currentNode=currentNode.getNext();

 83                 }

 84                 return (E)now.getE();

 85   /*              count++;

 86                 if (currentNode.getNext()==null){

 87                     curser++;

 88                 }else {

 89                     currentNode=currentNode.getNext();

 90                 }//这刚好链表上只有一个元素 没有修改currentNode 自己写bug

 91                 return currentNode.getE();*/

 92             }

 93         }

 94     }

 95     // 该内部类 实现 链表结构

 96     private class Node<E> {

 97         private E e;

 98         private Node next;

 99         public Node() {

100         }

101         public Node(E e, Node next) {

102             this.e = e;

103             this.next = next;

104         }

105         public E getE() {

106             return e;

107         }

108         public void setE(E e) {

109             this.e = e;

110         }

111         public Node<E> getNext() {

112             return next;

113         }

114         public void setNext(Node<E> next) {

115             this.next = next;

116         }

117     }

118 }

手写 HashSet的底层 和 迭代器的相关教程结束。