概念

  • Java中要用到数组的地方一般都用容器替代了。

接口图

  • Set 重复的话会被覆盖，即任意两个元素e1、e2都有e1.equals(e2)=false，因此存入Set的对象必须重写equals()和hashCode()。
  • Set 最多只能有一个null元素。
  • Set 只能遍历不能get得到某元素，因为无序无索引
  • List 可以重复。
  • List 有序。
  • List接口下还有一些子（实现）类

  • 数组：查询快

  • 链表：插入、修改快

  • ArrayList

    初始长度就是10，超容量后扩容

  • LinkedList

    链表实现

    其添加方法文档中为：void add(int index, E element);//尽管有索引但是查找的时候也是遍历的方式

  • list.get()

    返回Object类，需要强制转换

  • list.set(0)

    指定位置往里扔

Map

  • Map接口下也有一些子（实现）类

  • 无序、不可重复，因为它是无序的，所以需要通过key来查找，所以不能重复。

  • map.values()：返回值的Collection，不能向下转换（如强转为List），只能向上转为Object之类的父类。

public static void main(String[] args) {
    Map<String,String> map = new HashMap<String,String>();
    map.put("A", "A");
    map.put("B", "B");
    map.put("C", "C");
    map.put("D", "D");
    map.put("E", "E");

    //直接打印
    System.out.println(map.values()); //[A, B, C, D, E]

    //报错：java.util.HashMap$Values cannot be cast to java.util.List
    //List<String> valuesList = (List<String>) map.values();

    //向上转换
    //Object values=map.values(); //不过后面就不能直接遍历打印了

    //除了向上转换，也可以利用ArrayList的构造方法(Collection)传入一个Collection
    List<String> valuesList=new ArrayList<>(map.values());
    for(String str:valuesList){
        System.out.println(str); //A回车B回车...
    }
}
  • 代码示例：ideaProjects/shiro-chapter20/test/MapValuesTest、chapter20/codec/HmacSHA256Utils
  • 参考文章
  • 参考文章

HashMap

  • 无序，且不保证顺序恒久不变。
  • 底层是数组，数组元素是链表，因此查找容易，插入和删除也容易。
  • 当我们调用put()存储对象到HashMap时，它先调用键对象的hashCode()，返回hashCode作为索引；然后再调用equals()方法判断是否已有键的hashCode和当前的一样，一样则覆盖，否则存为新的键值对。
  • 当两个对象的hashCode相同时，它们也可能不相同，即equals()=false，还是需要存为新元素，此时HashMap把它们存在同个位置的链表下一结点中。
  • 而get()时，HashMap使用键对象的hashCode找到其在数组中的位置，接着调用key.equals()方法找到正确的结点。因此即使这一位置的链表中存在多个结点，HashMap也能找到正确的。
  • 允许使用null键和null值。
  • 线程不安全，效率高。

HashTable 线程安全，效率低

  • map.entrySet():获取一个个体为Map.Entry对象的Set集合，即Set<Map.Entry<k,V>>。Map.Entry包含getKay和getValue方法。
for(Map.Entry<String,String> entry:map.entrySet()){
    System.out.println(entry.getKey()+entry.getValue());
}
//或
Iterator i=map.entrySet().iterator();
while(i.hasNext()){
    System.out.println(i.next());
    //等同于下两行
    Map.Entry<String, String> entry = (Map.Entry<String, String>)i.next();
    System.out.println("key:" + entry.getKey() + " value" + entry.getValue());
}
  • map.keySet()：单独获取key的集合
Set keys = m.keySet( );
if(keys != null)
    for(String s : keys)
        t.append(s + ": " + m.get(s) + "/n");

方法实现

//重写equals方法，判断两个对象内容上是否相同，相同返回ture
public boolean equals(Object obj){
    if(this == obj)  //比较的是引用（地址），不同对象地址肯定不同，相同则肯定是同一个对象
        return ture;
    if(obj == null)
        return false;
    if(getclass() != obj.getclass())  //判断类型上是否相同，不相同也肯定不是相同对象
        return false;
    Person other = (person) obj;
    if(id != other.id)
        return false;
    return ture;  //都不是上面的情况表示相同，返回true
}

Map的底层实现

存入元素放入一个链表数组中，即元素为链表的数组，同一链表各结点hashcode相同（当链表太长时自动转换为红黑树，提高查找效率）

  • Object中有hashcode方法，也就意味着所有的类中都有hashcode方法

Set

HashSet的底层实现是HashMap
测试

Iterator迭代器

  • 集合内部一般都会实现Iterator接口以便遍历集合元素，下面模拟ArrayList内的迭代器实现
/**
 * @Author haien
 * @Description 模拟ArrayList内部类Itr对Iterator的实现
 * @Date 2018/10/23
 **/
public class MyIterator {
    //下一个元素的游标
    int cursor;
    //上一个元素的游标(cursor、lastRet在数组中的位置是相邻的)
    int lastRet=-1;
    //预期被修改（add/set/remove）的次数;modCount是外部类的属性,也是预期被修改的次数
    int exceptedModCount=modCount;

    final void checkForComodification(){
        //在调用Iterator遍历时，如果其他线程修改list则外部类的modCount会改变，但内部类的exceptedModCount不会，那么抛异常
        if(exceptedModCount!=modCount){
            throw new ConcurrentModificationException();
        }
    }

    public boolean hasNext(){
        return cursor!=size; //size是外部类的属性，是数组容量
    }

    //用过一次这个方法就相当于把一个元素给出栈了一样，而lastRet就相当于指着栈顶元素，cursor指着第二个元素
    public E next(){
        checkForComodification();
        //cursor指着当前要被返出去的元素
        int i=cursor;
        //尽管调用该方法前调用者会先检查是否hasNext()，但依然要做异常处理
        if(i>size){
            throw new NoSuchElementException();
        }
        //ArrayList实际是用一个数组来盛放元素的，迭代的时候要把这个数组拿到
        Object[] elementData=ArrayList.this.elementData;
        //可能i刚传进来elementData就在另一个线程里被删了一个元素
        if(i>=elementData.length){
            throw new ConcurrentModificationException();
        }
        cursor++;
        return (E)elementData[lastRet=i];
    }

    /**相当于栈顶元素出栈；调用方式一般为：
     * if("abc".equals(it.next()))
     * {
     *    it.remove();
     * }
     */
    public void remove(){
        if(lastRet<0){
            throw new IllegalStateException();
        }
        checkForComodification();
        //lastRet就是要删除的元素，remove方法不会改变lastRet，但会改modCount；删除元素后把后面的元素前移一位
        try {
            ArrayList.this.remove(lastRet);
            //前移之后lastRet就指着被删除元素的下一个元素了
            cursor = lastRet;
            lastRet = -1;
            exceptedModCount = modCount;
        }catch (IndexOutOfBoundsException e){ //溢出了一定是线程并发的问题
            throw new ConcurrentModificationException();
        }
    }

}
  • 代码实例：DataStructure/iterator/MyIterator