Java学习----Collection总结

  1. 云栖社区>
  2. 博客>
  3. 正文

Java学习----Collection总结

晓生寒 2018-11-01 17:05:44 浏览520
展开阅读全文

Java----Collection总结

集合,存储多个元素的容器----大小不定。
在集合这块主要的内容有:
接口:Collection Iterator List   Set  Map
类:ArrayList   LinkedList  stack queue
hashMap  hashTable


本篇为Collection的总结,才开始学习Java,在集合这块看资料总是感觉一团乱麻。所以写这个总结,一方面把自己知道的东西梳理一下,另一方面初学水平有限,如果有错误还请各位大神能够指点,还有就是刚开始玩社区,希望能够获取一点积分,嘿嘿。希望有一天,能够学习JAVA,加入Ali。

Collection接口

Collection是集合层次的根接口。由于泛型的限制,集合中只能存储对象。泛型只能表示引用类型。
Collection定义中的主要方法,就是说当要实现一个Collection的时候,要先实现以下方法(不全,可以查看API稳定):


public interface Collection<E> extends Iterable<E>{
  int size();
  boolean isEmpty();
  void clear();
  boolean contains();
  boolean add();
  boolean remove();
  Iterator<E> iterator();
}


实现一个Collection,在ArrayList中实现了List接口,而List接口继承了Collection接口,所以可以用下面方式来实现一个Collection集合,然后可以用上述方法。
Collection<String> c = new ArrayList<String>();


List接口

List接口是Collection的子接口,用于定义线性表数据结构。可以将List理解为存放对象的动态数组,只不过其元素个数可以动态的增加或者减少。List接口两个常见的实现类是ArrayList和LinkedList。分别用动态数组和链表的方式实现了List接口。(这两种实现方式在文末附上)

public interface List<E> extends Collection<E> {
Anytype get(int idx);
  Anytype set(int idx, Anytype newVal);
  void add(int idx, Anytype x);
  void remove(int idx);
  Iterator<Integer> listIterator(int pos);
}


重要方法:

List<E> list = new ArrayList<>();
E get(int idx) 获取集合中指定下标对应的元素
E set(int idx,E element) 给定下标上的元素,并将原来的元素返回
E add(int idx,E element) 在给定下标出添加元素,原位置及以后的元素都后移
E remove(int idx) 删除给定位置的元素,并将被删除的元素返回
List<E> sublist(int formIdx,int toIdx)获得List中的子序列(前包括,后不包括)

Object[] toArray()
<T> [] t  =  toArray(T[] a) 
String [] strArr = list.toArray(new String []()); 将List转成数组,第二种比较常用

static List<T> list = asList<T[]a>
String [] strArr = {"a","b","c"};
  List<String> list = Arrays.asList(strArr);将数组转换成list。

Iterator接口

public interface Iterator<E> {
  boolean hasNext();
  Anytype next();
  void remove();
}

迭代器用于遍历集合元素。获取迭代器,可以使用Collection中的方法,Iterator iterator()。具体用法如下代码。:

Set<String> set = new HashSet<String>();
  set.add("a");
  set.add("b");
  //建立一个指向set的迭代器
  Iterator<String> it = set.iterator();
  while(it.hasNext()){ 
   String str = it.next();
   System.out.println(str);
   //删除元素
   it.remove();
  }
 System.out.println(set);
注意:迭代器在遍历元素时,不能通过集合的remove方法来删除元素,否则会抛出异常。但是可以通过迭代器自身提供的方法的remove方法来删除,具体实现方式在LinkedList的实现代码中有。 


Collections 操作集


Collections操作集是为collection及其子接口、类提供操作方法的一个操作集。(几乎用不到)但是有sort()方法比较重要。
void sort(List<T> list);
直接使用该方法是自然排序,也可以使用Comparable 和Comparator。
Collection中的sort()能够排序的主要原因是,传入的集合元素都是Comparable接口的实现类,该接口表示子类是可以比较的,因为实现该接口重写抽象方法 int compareTo(T t);
该方法用于当前对象与给定对象进行比较:
 若当前对象大于给定对象,则返回值应为大于0的整数
 若当前对象小于给定对象,则返回值应为小于0的整数
 若两个对象相等,则返回值等于0
一旦java类实现了comparable接口,其比较规则就已经确定。如果想要在排序中临时指定规则,可以采用Comparator接口回调的方式,具体使用如下:

list.sort(new Comparator<String>(){
   //比较规则写在这
   //如果返回值>0,那么就会将o2排在o1之前
   //如果返回值<0,那么就会将o1排在o2之前
   public int compare(String o1,String o2){
    //return o1.compareTo(o2);
    return o1.charAt(0) - o2.charAt(0);
   }
  });

Set接口--散列集合

不包含重复元素的集合(唯一)
Set的具体用法跟list差不多,这里代码不再重复写。
Set<String> set = new HashSet<String>();
HashSet
底层基于hashMap来进行存储,不保证迭代顺序,并且不保证循序不变。
HashMap
是基于数组+链表来进行存储。底层数组初始容量为16.数组中的每一个位置称之为是一个桶-bucket
O1---先计算o1的hash码--哈希码是int类型的整数--针对哈希码进行二次运算,使运算结果落在桶的编号之中。
每一个桶中维系了一个链表。添加新元素时,先比较与桶中的元素是否相等,不相等,加入到链表,有相等就舍弃。放的越晚的元素,比较就越低,增删改效率都会降低。所以想要缩短链的长度,就得增加桶的个数。扩容,每次都是一倍。
如果已经使用的桶的数量/桶的总数量>加载因子,那么就认为需要扩容。默认加载因子是0.75。扩容之后,会对桶中的元素进行重新的计算和分布,是元素散列在新找的桶中--rehash。
Rehash---元素越多,效率越低。当你进行rehash的时候,是不能往里面放元素的。
加载因子:影响扩容,越小会扩容越频繁。同时会导致内存的浪费。效率变低。加载因子越大,会导致每一个桶汇中的链表会变长而导致查找变慢。
public HashSet(int initialCapacity),允许指定初始容量和加载因子。
总的效率,一开始是高的,然后慢慢变慢。在JDK1.8中,如果链的长度>8,那么会将这个链扭转成红黑树,自平衡二叉树。红黑树,比节点小,往左放,比节点大,往右放,类似二分查找。如果红黑红树的节点个数<=6,会扭回链表。

Map接口

一组自变量按照某种规则变成另外一组因变量,就叫做映射。
K -key-键,V-value-值。一个键对应一个值 - 键值对。也就意味着,一个映射实际上是由多个键值对组成。在映射中,键是唯一的。一个键最多只能对应一个值。
实现类HashMap与HashTab

HashMap<K,V>

底层是基于数组+链表的结构。允许键或者值为null。默认初始容量是16,加载因子是0.75.。这个类不保证数据的顺序map是计算key的哈希码,可以针对哈希码来进行二次运算,决定存到哪个桶中。尤其是不保证这个顺序恒久不变。默认rehash扩容,每次会增加大约两倍空间。如果是一个比较高的加载因子,
hashMap允许指定初始容量。指定的初始容量在[2^x , 2^x+1]之间,那么容量算出来的一定是为2^x+1。指定这么大是为了扩容的时候,直接左移一位。本身是一个异步式线程不安全的映射。
异步式:如果一个对象在同一个时刻内允许多人操作
同步式:如果一个对象在一个时刻内允许一个人操作

Map<String, Integer> map = new HashMap<>();
  map.put("d",6);
  map.put("e",4);
  map.put("s",3);
  map.put("f",9);
map.put("i",4);
  //如果键值相同,对应的值覆盖
  map.put("i", 3);
  
  //判断是否包含这个键
  System.out.println(map.containsKey("a"));
  System.out.println(map.containsValue(7));
  //移除键值对
  map.remove("i");
  //如果键相同,那么对应的值覆盖
  
  //清空映射
  map.clear();
  
  //获取指定的键所对应的值
  System.out.println(map.get("r"));
  
  //将映射中所有的值放入一个集合返回
  Collection<Integer> c = map.values();
 System.out.println(c);

HashTbale

不允许键或者值为null.底层也是基于数组+链表。底层的默认初始容量是11.加载因子为0.75F,默认扩容增加一倍,然后再+1。(官方没有解释为什么这样)
这个映射本身是一个同步式线程安全的映射。
指定初始容量,指定多少,就是多少。
基本上没有用,效率比较低,只会出现在面试的时候。

List接口 自己写的LinkedList的实现


package ADT;

import java.security.NoSuchAlgorithmException;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.lang.String;

public class myLinkedList<String> implements Iterable<String> {

	private static class Node<String> {
		public Node(String d, Node<String> p, Node<String> n) {
			data = d;
			prev = p;
			next = n;
		}

		public String data;
		public Node<String> prev;
		public Node<String> next;

	}

	public myLinkedList() {
		doclear();
	}

	public void clear() {
		doclear();
	}

	public void doclear() {
		beginMarker = new Node<String>(null, null, null);
		endMarker = new Node<String>(null, beginMarker, null);
		beginMarker.next = endMarker;

		theSize = 0;
		modCount++;
	}

	public int size() {
		return theSize;
	}

	public boolean isEmpty() {
		return size() == 0;
	}

	public boolean add(String x) {
		add(size(), x);
		return true;
	}

	public void add(int idx, String x) {
		addBefore(getNode(idx, 0, size()), x);
	}

	public String get(int idx) {
		return getNode(idx).data;
	}

	public String set(int idx, String val) {
		Node<String> p = getNode(idx);
		String oldval = p.data;
		p.data = val;
		return oldval;
	}

	public String remove(int idx) {
		return remove(getNode(idx));
	}

	private void addBefore(Node<String> p, String x) {
		Node<String> newnode = new Node<>(x, p.prev, p);
		newnode.prev.next = newnode;
		p.prev = newnode;
		theSize++;
		modCount++;
	}

	private String remove(Node<String> p) {
		p.prev.next = p.next;
		p.next.prev = p.prev;
		theSize--;
		modCount++;
		return p.data;
	}

	private Node<String> getNode(int idx) {
		return getNode(idx, 0, size() - 1);
	}

	private Node<String> getNode(int idx, int low, int up) {
		Node<String> p;
		if (idx < low || idx > up) {
			throw new IndexOutOfBoundsException();
		}
		if (idx < size() / 2) {
			p = beginMarker;
			for (int i = 0; i < idx; i++)
				p = p.next;
		} else {
			p = endMarker;
			for (int i = size(); i > idx; i--)
				p = p.prev;
		}
		return p;
	}

	@Override
	public Iterator<String> iterator() {
		// TODO Auto-generated method stub
		return new LinkedIterator();
	}

	private class LinkedIterator implements Iterator<String> {
		private Node<String> current = beginMarker.next;
		private int exceptedModecount = modCount;
		private boolean okToRemove = false;

		@Override
		public boolean hasNext() {
			// TODO Auto-generated method stub
			return current != endMarker;
		}

		@Override
		public String next() {
			// TODO Auto-generated method stub
			if (modCount != exceptedModecount)
				throw new ConcurrentModificationException();
			if (!hasNext())
				throw new NoSuchElementException();
			String nextItem = current.data;
			current = current.next;
			okToRemove = true;
			return nextItem;
		}

		public void remove() {
			if (modCount != exceptedModecount)
				throw new ConcurrentModificationException();
			if (!okToRemove)
				throw new IllegalStateException();
			myLinkedList.this.remove(current.prev);
			exceptedModecount++;
			okToRemove = false;
		}

	}

	@Override
	public java.lang.String toString() {

		StringBuilder sb = new StringBuilder("[");

		Node node = this.beginMarker;
		while (node != null) {

			sb.append(node.data).append(", ");
			node = node.next;

		}

		java.lang.String str = sb.toString();
		if (size() != 0)
			str = str.substring(0, str.length() - 2);

		return str += "]";
	}

	private Node<String> beginMarker;
	private Node<String> endMarker;
	private int theSize;
	private int modCount = 0;
}


网友评论

登录后评论
0/500
评论
晓生寒
+ 关注