1. ArrayList

1.1 增删改查

方法	ArrayList
初始化	List<X> arrayList = new ArrayList(); List<X> arrayList = new ArrayList(initialSize); List<X> arrayList = new ArrayList(Collection) 备注：Collection包括List、ArrayList、Vector、LinkedList、Set、HashSet、TreeSet;
增	add(E e)：该方法是将指定的元素添加到列表的尾部。当容量不足时，会调用 grow 方法增长容量。 add(int index, E element)：在 index 位置插入 element,注意这个不是覆盖，会把后面的元素都向后靠一个位置。 addAll(Collection<? extends E> c) 和 addAll(int index, Collection<? extends E> c)：将特定 Collection 中的元素添加到 Arraylist 末尾。
删	boolean remove(int index): 该方法首先调用rangeCheck(index)来校验 index 变量是否超出数组范围，超出则抛出异常。删除第index个元素，整体左移，返回oldValue。 boolean remove(Object o): 删除list中首次出现的元素o（可以为null），返回boolean值，成功为true，失败为false。 clear(): 从列表中移除所有元素。 removeAll(Collection<? extends E> c): 从列表中移除指定 collection 中包含的所有元素。
改	set(int index, E element)：该方法首先调用rangeCheck(index)来校验 index 变量是否超出数组范围，超出则抛出异常。而后，取出原 index 位置的值，并且将新的 element 放入 Index 位置，返回 oldValue。
查	get(int index):查找第index个元素并返回。 indexOf(Object o):返回列表中首次出现指定元素的索引,如果列表不包含此元素,则返回 -1。 lastIndexOf(Object o):返回列表中最后一次出现指定元素的索引,如果列表不包含此元素,则返回 -1。 List subList(int fromIndex, int toIndex): 返回列表中指定的fromIndex(包括)和toIndex(不包括)之间的部分。 toArray(): 返回以正确顺序包含列表中的所有元素的数组。

1.2 遍历

3种遍历方式：

1.2.1 for循环下标遍历

1
2
3

for(int i = 0; i < list.size(); i++){
    System.out.println(list.get(i));
}

1.2.2 for循环直接遍历

1
2
3

for(String tmp : list){
    System.out.println(tmp);
}

1.2.3 iterator遍历

1
2
3

for(Iterator it2 = list.iterator();it2.hasNext();){
    System.out.println(it2.next());
}

1.3 排序

这里只使用Collections.sort()方法，默认是升序，如需要降序，则需要重写Comparator。

public class SortArrayListAscendingDescending {
    private ArrayList arrayList;
    // 升序排列
    public ArrayList sortAscending() {
        Collections.sort(this.arrayList);
        return this.arrayList;
    }
    // 降序排列
    public ArrayList sortDescending() {
        Collections.sort(this.arrayList, Collections.reverseOrder());
        return this.arrayList;
    }
}

如何重写comparator，使用comparator排序呢？这里需要重写compare方法，比较o1和o2两个对象，返回int值，默认的升序排序规则是：如果o1 > o2返回1，o1 < o2返回-1，o1 == o2返回0。下面代码是降序排序器的代码

public class Mycomparator implements Comparator {

    public int compare(Integer o1, Integer o2) {
        if (o1 < o2) return 1;
        else if (o1 > o2) return -1;
        else return 0;
    }
}

public class ListSort {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList();
        list.add(1);
        list.add(2);
        list.add(-1);
        Comparator comp = new Mycomparator();
        Collections.sort(list, comp);
    }
}

2. HashMap & HashTable

3. HashSet

3.0 实现原理

HashSet的底层实现是由HashMap来实现的，对于其所添加的对象，可能用到以下几种方法。

equals()方法
用来实现Set中元素的不重复性，如果不覆盖（override）equals()方法，默认使用父类Object的equals方法，则只是比较对象的引用是否相同。
hashCode()
hashCode()方法时为了实现HashSet和LinkedHashSet而实现的。只有知道对象的hash值，才能根据这个hash值确定存放在散列表的槽的index。同样，如果不覆盖（override）hashCode()方法，默认使用父类Object的hashCode()方法。
toString()方法
toString()方法在打印对象时会调用。如果不覆盖（override）toString()方法，默认使用父类Object的。
compareTo()方法
用户类要实现Comparable接口。这个方法主要用于将对象存放在TreeSet()时保证顺序的。由于是接口，所以用户类必须要实现这个方法。

继承关系：

1
2

|--HashSet 底层是由HashMap实现的，通过对象的hashCode方法与equals方法来保证插入元素的唯一性，无序(存储顺序和取出顺序不一致)，。
    |--LinkedHashSet 底层数据结构由哈希表和链表组成。哈希表保证元素的唯一性，链表保证元素有序。(存储和取出是一致)

实现原理:

往Haset添加元素的时候，HashSet会先调用元素的hashCode方法得到元素的哈希值，然后通过元素的哈希值经过移位等运算，就可以算出该元素在哈希表中的存储位置。见下面2种情况：

如果算出元素存储的位置目前没有任何元素存储，那么该元素可以直接存储到该位置上。
如果算出该元素的存储位置目前已经存在有其他的元素了，那么会调用该元素的equals方法与该位置的元素再比较一次，如果equals返回的是true，那么该元素与这个位置上的元素就视为重复元素，不允许添加，如果equals方法返回的是false，那么该元素运行添加。

3.1 增删改查

方法	HashSet
初始化	HashSet() 构造一个新的空 set，其底层 HashMap 实例的默认初始容量是 16，加载因子是 0.75。 HashSet(Collection<? extends E> c) 构造一个包含指定 collection 中的元素的新 set。 HashSet(int initialCapacity) 构造一个新的空 set，其底层 HashMap 实例具有指定的初始容量和默认的加载因子（0.75）。 HashSet(int initialCapacity, float loadFactor) 构造一个新的空 set，其底层 HashMap 实例具有指定的初始容量和指定的加载因子。备注：Collection包括List、ArrayList、Vector、LinkedList、Set、HashSet、TreeSet;
增	boolean add(Object o)：该方法用于向集合里添加一个元素。 boolean addAll(Collection c)：该方法把集合c里的所有元素添加到指定集合里。
删	void clear()：清除集合里的所有元素，将集合长度变为0。 boolean remove(Object o)：删除集合中的指定元素o，当集合中包含了一个或多个元素o时，这些元素将被删除，该方法将返回true。 boolean removeAll(Collection c)：将集合中删除集合c里包含的所有元素（相当于用调用该方法的集合减集合c），如果删除了一个或一个以上的元素，则该方法返回true。 boolean retainAll(Collection c)：将集合中删除集合c里不包含的元素（相当于把调用该方法的集合变成该集合的集合c的交集），如果该操作改变了调用该方法的集合，则该方法返回true。
改	Object[] toArray()：该方法把集合转换成一个数组，所有的集合元素变成对应的数组元素。
查	boolean contains(Object o)：返回集合里是否包含指定元素。 boolean containsAll(Collection c)：返回集合里是否包含集合c里的所有元素。

3.2 遍历

Iterator迭代方式遍历

Set<String> set = new HashSet<String>();  
set.add("aaa");  
set.add("bbb");  
set.add("ccc");    
Iterator iterator = set.iterator();  
while (iterator.hasNext()) {  
System.out.println(iterator.next());
}

for循环方式遍历

Set<String> set = new HashSet<String>();  
set.add("aaa");  
set.add("bbb");  
set.add("ccc");  
for (String s:set) {  
System.out.println(s);  
}

3.3 排序

4. Queue

5. Stack

6. Heap

7. TreeMap

2020-05-19 09:19:12 # 知识点总结 # stack # heap # list # map # queue # set