文章目录
Set接口及其实现类
Set接口继承了Collection接口。
Set中所存储的元素是不重复的, Set中的元素是没有索引的.
Set接口有两个实现类;HashSet,TreeSet.
HashSet
HashSet是无序的(即不是按照添加元素的顺序进行排列的).默认长度为16;负载因子为0.75;即元素填充到3/4时就会开始扩容,扩容速度为2倍.
在HashSet的底层实际上就是应用了HashMap;Map是双列存储的(即键值对(key |value)
的方式);而Set是单列存储的;HashSet只是使用了HashMap的键
那个列;是从HashMap中扩展出来的,一个单列存储的类.
底层源码:
未添加元素时;
HashSet底层;哈希表(本质上也是数组,不过里面有了Node节点(包括数据域和指针)来存储数据),链表,红黑树
在使用add方法添加元素时,里面return的是map.put(e, PRESENT)==null;
调用了public V put(K key, V value)
方法;将key值传到hash( )函数中;通过return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
根据内容的hash值计算得出添加的这个元素在哈希表的位置;如果两个元素的位置计算出来在同一个位置,那么他们会通过Node节点中的指针进行指向链接,形成链表结构
;当这个链表叠加到8个时,又会转为红黑树结构.
元素不会重复出现
HashSet<String> h1=new HashSet<>();
h1.add("a");
h1.add("b");
h1.add("d");
h1.add("p");
h1.add("f");
h1.add("通话");//和b在同一个位置
h1.add("b");
h1.add("重地");//和b在同一个位置
System.out.println(h1);
//[p, a, b, 通话, 重地, d, f]
关于HashSet如何保证元素不会重复.
先用元素的哈希值进行比较;但是内容不同时;哈希值可能相同(虽然效率快,但是安全性过低)
;当哈希值相同内容不同时(hash碰撞,hash冲突),使用equals方法进行比较内容是否相等(双重保证,提升了安全性
)
注意这个计算Hsah值的时候,如果类中没有重写equals方法
,会调用Object类中的hashCode方法;这个时候的hash值在计算出来实际上是对象在内存中的地址,即使内容相同,它也会计算出不同的hash值,这就使得相同的元素存储进去了.
而类中如果有重写的hashCode方法
时,就会有一套hash计算方法对内容进行计算.
HashSet中的几个常用方法
返回值类型 | 方法 |
---|---|
boolean | add(E e) 将指定的元素添加到此集合(如果这个元素尚未存在时) |
void | clear( ) 清空集合中所有元素。 |
Object | clone() 返回此 HashSet实例的浅层副本:元素本身不被克隆。 |
boolean | contains(Object o) 如果此集合包含指定的元素,则返回值 true 。 |
boolean | isEmpty() 如果此集合不包含元素,则返回 true 。 |
Iterator< E> | iterator( ) 返回此集合中元素的迭代器。 |
boolean | remove(Object o) 从集合中删除指定的元素。 |
int | size() 返回此集合中的元素个数(其基数)。 |
TreeSet
TreeSet可按照元素的自然顺序排列;TreeSet底层结构是红黑树(即一种自平衡的二叉树).不能存储重复元素
在添加元素时存储的对象必须实现Comparable接口。然后重写了CompareTo方法(是被TreeSet的添加方法底层调用),来保证按照指定顺序进行排序
在底层使用了TreeMap
TreeSet的方法
返回值类型 | 方法 |
---|---|
boolean | add(E e) 将指定的元素添加到此集合(如果尚未存在) |
boolean | addAll(Collection<? extends E> c) 将指定集合中的所有元素添加到此集合中。 |
E | ceiling(E e) 返回此集合中最小元素大于或等于给定元素,如果没有此元素,则返回 null 。 |
void | clear() 清空集合中所有元素。 |
Object | clone() 返回此 TreeSet实例的浅拷贝。 |
Comparator<? super E> | comparator( ) 返回用于对该集合中的元素进行排序的比较器,或null |
boolean | contains(Object o) 如果此集合包含指定的元素,则返回 true 。 |
Iterator< E> | descendingIterator() 以降序返回该集合中的元素的迭代器。 |
Iterator< E> | iterator() 以升序返回该集合中的元素的迭代器。 |
E | first( ) 返回此集合中当前的第一个(最低的)元素。 |
E | last( ) 返回此集合中当前的最后一个(最高的)元素。 |
E | floor(E e) 返回此集合中最大的元素小于或等于给定元素,如果没有这样的元素,则返回 null 。 |
SortedSet< E> | headSet(E toElement) 返回此集合的部分的视图,其元素严格小于 toElement 。 |
NavigableSet< E> | descendingSet() 返回此集合中包含的元素的反向排序视图。 |
E | higher(E e) 返回严格大于给定元素的该集合中的最小元素,如果没有此元素则返回 null 。 |
E | lower(E e) 返回这个集合中最大的元素严格小于给定的元素,如果没有这样的元素,则返回 null 。 |
boolean | isEmpty( ) 如果此集合不包含元素,则返回 true 。 |
E | pollFirst( ) 检索并删除第一个(最低)元素,或返回 null如果该集合为空。 |
E | pollLast() 检索并删除最后一个(最高)元素,如果此集合为空,则返回 null 。 |
boolean | remove(Object o) 如果存在,则从该集合中删除指定的元素。 |
int | size() 返回此集合中的元素数(其基数)。 |
NavigableSet< E> | subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) 返回该集合的部分的视图,其元素的范围从 fromElement到 toElement 。 |
SortedSet< E> | subSet(E fromElement, E toElement) 返回此集合的部分的视图,其元素的范围从 fromElement (含)到 toElement |
SortedSet< E> | tailSet(E fromElement) 返回此集合的元素大于或等于 fromElement的部分的视图。 |
NavigableSet< E> | tailSet(E fromElement, boolean inclusive) 返回此集合的部分的视图,其元素大于(或等于,如果 inclusive为true) fromElement 。 |
Set接口的迭代
以TreeSet为例,有一个TreeSet集合String类型的t1;有5个元素[A, a, b, c, d].
通过一个方法迭代
//1.public java.util.stream.Stream<E> stream()
//最终以流的方式输出;
t1.stream().forEach((a)-> System.out.println(a));
增强For循环
//2.增强for循环
for(String f:t1){
System.out.println(f);
}
迭代器遍历
//3.迭代器遍历
//public interface Iterator<E>
//首先获取迭代器对象;
Iterator<String> iterator=t1.iterator();
//这里使用迭代器的hasNext方法,进行判断集合中还有没有下一个元素;
//public abstract boolean hasNext()
while(iterator.hasNext()){
//如果有就使用迭代器的next方法向下移动指针,并且返回指针指向的元素;
String s=iterator.next();
System.out.println(s);
}