Java基础之常用集合及排序_java hashset 排序

本文来自刘兆贤的博客_CSDN博客-Java高级,Android旅行,Android基础领域博主 ，引用必须注明出处！

大家好，今天我们来讲一下常用的集合类，如ArrayList、HashMap、HashSet、LinkedList

同步：即多个线程访问一个实例，如果一个线程对实例进行修改，则实例发生改变

Hashmap：是一个键值对组合，允许多个空值和一个空键的出现，可同步，不安全。

使用链表保存，当前key的值已经保存7个时，则改用红黑树进行保存。

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
 
    /**
     * Implements Map.put and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

HashMap有两种遍历方法：

		// 第一种:
		Map<Object, Object> map = new HashMap<Object, Object>();
		for (int i = 0; i < 10000; i++) {
			map.put(it, i);
		}
		Iterator<Entry<Object, Object>> iter = map.entrySet().iterator();
		long time=System.currentTimeMillis();
		while (iter.hasNext()) {
			Entry<Object, Object> entry = iter.next();
			Object key = entry.getKey();
			Object val = entry.getValue();
		}
		long time2=System.currentTimeMillis();
		// 第二种:
		Iterator<Object> iter2 = map.keySet().iterator();
		while (iter2.hasNext()) {
			Object key = iter2.next();
			Object val = map.get(key);
		}
		long time3=System.currentTimeMillis();
		System.out.println("(time3-time2)>(time2-time)："+((time3-time2)>(time2-time)));

运行结果：

(time3-time2)>(time2-time)：false

很显然，第二种方法要比第一种方法快，是一种轻量级的处理方式。

Hashset：不允许有重复元素，不同步，线程安全，可自动排序，与List用法相似。

有关HashSet：

		HashSet<Integer> set = new HashSet<Integer>();
		set.add(2);
		set.add(1);
		set.add(4);
		set.add(2);
		Iterator<Integer> it = set.iterator();
		while(it.hasNext()){
			System.out.println(it.next());
		}

执行结果：

1
2
4

说明两个问题，第一、HashSet是不允许重复数据的，第二、HashSet是自动排序的

 

ArrayList：查找数据快，由其数组结构决定，是动态数组而非链表，有下标。底层由数组支持。

增长时，为当前长度的一半

Vector：线程安全，每次操作时方便都用synchronized包裹。增长时，为当前长度的一倍。

LinkedList：增加、删除数据快，而查找数据慢，前一个元素带有后一个元素的索引。底层由双向链表实现。

最有争议的是修改这一块，关于修改，它其实是删除+增加，理论上说是LinkedList要快一点。

		ArrayList<Integer> list = new ArrayList<Integer>();
		for (int i = 0; i < 1000000; i++) {
			list.add(i);
		}
		LinkedList<Integer> list2 = new LinkedList<Integer>();
		for (int i = 0; i < 1000000; i++) {
			list2.add(i);
		}
		long time4 = System.currentTimeMillis();
		list.remove(100);
		list.add(100, 9000);
		long time5 = System.currentTimeMillis();
		list2.remove(100);
		list2.add(100, 9000);
		long time6 = System.currentTimeMillis();
		System.out.println("(time6-time5)>(time5-time4)："
				+ ((time6-time5)>(time5-time4)));
	}

运行结果：

(time6-time5)>(time5-time4)：false

很显然LinkedList要比ArrayList修改要快。

下面是有关List集合中对象排序的问题：

ArrayList和LinkedList是两个集合类，一般查找数据操作多需要用前者，删除插入操作多的要用后者。

方法一：

主程序：

package test.test5;


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

 //按姓名的长度排序

public class SortByName {

public static void main(String[] args) {
// Student stu1 = new Student(23, "fred");
// Student stu2 = new Student(29, "frankie");
// Student stu3 = new Student(27, "gv");
// Student stu4 = new Student(28, "terry");
Student stu1 = new Student(23, "刘L中");
Student stu2 = new Student(29, "魏W");
Student stu3 = new Student(27, "张");
Student stu4 = new Student(28, "杨Y史泰龙");
List<Student> list = new ArrayList<Student>();
list.add(stu1);
list.add(stu2);
list.add(stu3);
list.add(stu4);
Collections.sort(list);
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i).name + ":" + list.get(i).age);
}
}
}

结果：

张:27
魏W:29
刘L中:23
杨Y史泰龙:28

Bean程序：

package test.test4;


import test.test3.PinYin;

//要实现其Comparable接口
public class Student implements Comparable<Student> {
public int age;
public String name;


public int getAge() {
return age;
}


public void setAge(int age) {
this.age = age;
}


public String getName() {
return name;
}


public void setName(String name) {
this.name = name;
}


public Student(int age, String name) {
super();
this.age = age;
this.name = name;
}

//如果需要从小到大的排序，需要用本对象与传过来的对象进行比较

@Override
public int compareTo(Student o) {
// TODO Auto-generated method stub
int a = o.name.length();
int b = this.name.length();
return b - a;
}

}

方法二：

package test.test5;


import java.util.Collections;
import java.util.Iterator;
import java.util.Vector;


public class VectorTest {
public static void main(String[] args) {
Vector<String> v = new Vector<String>();
// 把对象加入Vector
v.add("ab");
v.add("ef");
v.add("cd");
v.add("ij");
v.add("gh");
// 排序
Collections.sort(v);// Collections.sort给集合排序，根据元素的自然顺序 对指定列表按升序进行排序。
// 输出
Iterator<String> it = v.iterator();// 返回以正确顺序在此列表的元素上进行迭代的迭代器。
while (it.hasNext()) {// 遍历iterator
String t = (String) it.next();// 向下读取一个iterator
System.out.println(t);
}
}
}

源码：集合对象排序-Android代码类资源-CSDN下载

Java容器的深入研究：

ConcurrentMap接口及其实现ConcurrentHashMap均用于多线程机制。

CopyOnWriteArrayList和CopyOnWriteArraySet也是用于多线程机制的。

LinkedHashSet以插入元素的顺序保存数据，代价要比HashSet高

TreeSet按照降序保存数据，要实现Comparator接口，一般只有用于一个排好序的Set时才会用到它。

SortedSet按照Comparator来排序保存数据

LinkedList和PriorityQueue是Queue的实现类，差异在排序而非性能，前者无序后者升序

LinkedList是双向队列，可以前后分别插入和删除数据，区别于底层由数组实现的ArrayList

HashMap是通过hashCode来实现快速查询的

SortedMap使键处于始终排序的状态

LinkedHashMap为提高速度，散列化所有元素，插入时比HashMap慢一点

SlowMap是最慢的查询方式

hashCode对于同一个对象的调用都是一样的，如果程序中有多个String对象，且包含相同的字符串，则它们共用一块内存

HashSet效率要比TreeSet好，同时它是自动排序的

WeakHashMap允许垃圾回收器自动清理键和值，触发条件：不再需要此键

Stack：pop返回首对象并删除之，peek返回首对象并不删除，push将值放入栈顶