collection集合和源码

collection集合和源码,第1张

collection集合和源码 集合 collection集合 map list集合三种循环
 List list = new ArrayList<>();
        list.add("1");
        list.add("2");
        list.add("3");
        //1.常用的循环
        for (int i = 0; i < list.size(); i++) {
            String o = list.get(i);
            System.out.println(o);
        }
        System.out.println("=====================");
        //2.增强for
        for (String s : list) {
            System.out.println(s);
        }
        System.out.println("=====================");
        //3.迭代器删除,会把本次的结果删除,下次使用的时候结果为空
        Iterator iterator = list.iterator();
        while ( iterator.hasNext() ) {
            String next = iterator.next();
            iterator.remove();
            System.out.println(next);
        }
        System.out.println(list.size());
        System.out.println("=====================删除后测试遍历,结果为空");
        for (String s : list) {
            System.out.println(s);
        }
        //总结:增强for环境的本地就是迭代器,会编译成迭代器,可以查询编译后的代码
        // Iterator iterator = list.iterator();
        //
        // while(iterator.hasNext()) {
        //     next = (String)iterator.next();
        //     System.out.println(next);
        // }
        //
        // System.out.println("=====================");
        // iterator = list.iterator();
        //
        // while(iterator.hasNext()) {
        //     next = (String)iterator.next();
        //     System.out.println(next);
        // }

练习list排序
public static void main(String[] args) {
        List list = new ArrayList<>();
        list.add(new UserEntity("qwe",12));
        list.add(new UserEntity("q",7));
        list.add(new UserEntity("e",9));
        list.add(new UserEntity("w",7));
        //从小到大排序,年龄
        sort(list);
        for (Object o : list) {
            System.out.println(o);
        }
    }
    //冒泡排序
    private static void sort(List list){
        for (int i = 0; i < list.size()-1; i++) {
            for (int j = 0; j < list.size()-1-i; j++) {
                //
                UserEntity o = (UserEntity)list.get(j);
                UserEntity o1 = (UserEntity)list.get(j+1);
                if (o.getAge()> o1.getAge()) {
                    list.set(j,o1);
                    list.set(j+1,o);
                }
            }
        }
    }
 
list源码 
ArrayList是Array(动态数组)的数据结构,linkedList是link(链表)的数据结构。
	当随机访问List(get和set *** 作)时,ArrayList比linkedList的效率更高,因为linkedList是线性的数据存储方式, 所以需要移动指针从前往后依次查找。
     当对数据进行增加和删除的 *** 作(add和remove *** 作)时,linkedList比ArrayList的效率更高,因为ArrayList是数组,所以在其中进行增删 *** 作时,会对 *** 作点之后所有数据的下标索引造成影响,需要进行数据的移动。
     ArrayList自由性较低,因为它需要手动的设置固定大小的容量。linkedList自由性较高,能够动态的随数据量的变化而变化
三、list 接口。顺序是一样的,可重复。
四、set 不能保证元素的排列顺序。不允许包含相同的元素
arraylist和linkedlist是线程不安全,vector 线程安全
   //arraylist
   public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    //linkedlist
     public boolean add(E e) {
        linkLast(e);
        return true;
    }
    //vector
      public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }
结论:
arraylist 空构造器,elementData初始化为0 ,第一次是10,第二次是1.5倍。不是空构造器,第一次是1.5倍。
vector    空构造器第一次是10,第二次是2倍。不是空构造器,第一次是2倍
结果验证 arraylist无参构造器验证
		ArrayList objects = new ArrayList<>();
        //添加1-10
        for (int i = 1; i <= 10; i++) {
            objects.add(i);
        }
        //添加11-15
        for (int i = 11; i <= 15; i++) {
            objects.add(i);
        }
        objects.add(100);
 
1.初始化容量 
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
    //创建一个空的数组
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
2.装箱过程
public static Integer valueOf(int i) {
        if (i >= IntegerCache.low && i <= IntegerCache.high)
            return IntegerCache.cache[i + (-IntegerCache.low)];
        return new Integer(i);
    }
3.执行add *** 作
public boolean add(E e) {
    //先确认是否要扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
    //然后再赋值 *** 作
        elementData[size++] = e;
        return true;
    }
4.是否扩容
private void ensureCapacityInternal(int minCapacity) {
    //是否要真的扩容
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
//比较取最大的值,第一扩容位10 
private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
        }


private void ensureExplicitCapacity(int minCapacity) {
    //记录修改的次数,防止多个线程修改
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            //扩容
            grow(minCapacity);
    }
5.扩容
private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
    //oldCapacity + (oldCapacity >> 1)==1.5倍。向右移除以2
        int newCapacity = oldCapacity + (oldCapacity >> 1);
    //注意第一次比较特别。 newCapacity = minCapacity;
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // Arrays.copyOf采用这个是为了保留之前的数据,在原来的基础上扩容
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

如果debugger过程中出现null,不显示,按照图示

arraylist有参构造器验证 1.容量是指定容量
 public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
其余的步骤都是一样的 vector无参构造 1.初始化容量
 public Vector() {
        this(10);
    }
2.这里主要记录不一样的地方,其他地方大同小异
 private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
     //扩容的倍数为2被倍  oldCapacity+oldCapacity
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
vector有参构造
也是一样的
linkedList双向链表

linkedList有两个属性分别维护了,一个头节点(first)和尾节点(last)。里面node对象 item; next; prev;通过prev指向前一个,next指向后一个

linkedList源码
 List objects = new linkedList<>();
        objects.add(1);
        objects.add(2);
 
1.初始化空 
public linkedList() {
    }
2.添加元素
  public boolean add(E e) {
        linkLast(e);
        return true;
    }
   void linkLast(E e) {
        final Node l = last;
        final Node newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

3.再次添加元素

总结:arraylist改查效率比较高,linkedlist增删效率比较高 set源码
List集合是有序存储,Set集合是无序存储。这里的有序和无序针对的是存储地址来说的。
	List可以存储重复的值,Set不可以存储重复的值,可以存入null
	hashset实际是hashmap
	TreeSet可以确保集合元素处于排序状态

public class test {
    public static void main(String[] args) {
        Node[] table = new Node[16];

        //在索引为2,china
        Node noddJohn=new Node("china",null); 
        table[2] = noddJohn;
        Node noddJack=new Node("us",null);  
        noddJohn.next=noddJack;
        Node noddRose=new Node("shanxi",null); 
        table[3] = noddRose;

    }

}
class Node{ //节点存储数据
     Object item;  //存放数据
     Node next; //指向下一个元素

    public Node(Object item, Node next) {
        this.item = item;
        this.next = next;
    }
}

1.hashset的底层是hashmap。
2.添加一个元素,会先计算hash值转换成索引值。
3.找到这个table中,看位置是否有元素
4.没有直接加入,有的,调用equals方法比较,相同覆盖,不同添加。
5.在Java8中链表大于等于8并且table长度大于等于64,转化成红黑树
如果hash值相同,就会加入链表。
 public static void main(String[] args) {
        Set set=new HashSet();
        set.add("java");
        set.add("c");
        set.add("java");
        System.out.println(set);
    }
1.初始化
  public HashSet() {
        map = new HashMap<>();
    }
2.添加
 public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

public V put(K key, V value) {
    //计算hash值
        return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node p; int n, i;
    //第一次计算链表是否为空,为空,则进行扩容 resize(扩容的大小为16,实际的大小为16*0.75,为了防止多线程)
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
    //通过hash值计算该元素,存放的索引位置,为空,存放改元素
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node e; K k;
            //链表的第1个p.hash计算索引的位置的hash和传进来计算的hash。==比较的是内存地址,
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //判断该元素是否为树
            else if (p instanceof TreeNode)
                e = ((TreeNode)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();
    //方法是个空的,为了hashmap的子类使用
        afterNodeInsertion(evict);
        return null;
    }
总结:HashSet 无序复杂度都是O(1) ,TreeSet复杂度O(log(n))【TreeSet是有序的,而Dog类不是有序的,我们需要将Dog类实现Comparable接口】,元素是有序。linkedHashSet时间复杂度是O(1),插入的顺序进行输出。 hashmap循环
Map map =new HashMap();
        map.put(1, "xiao");
        map.put(2, "chao");
        map.put(3, "shang");
        map.put(4, "xue");
        for(Map.Entry entry : map.entrySet()) {
            System.out.println("方法一:key ="+entry.getKey()+"---value="+entry.getValue());
        }

        //方法二
        for(Integer key:map.keySet()) {
            System.out.println("方法二:key = "+key);
        }

        for(String value:map.values()) {
            System.out.println("方法二:value = "+value);
        }
        //方法三
        Iterator> entries = map.entrySet().iterator();
        while(entries.hasNext()) {
            Map.Entry entry = entries.next();
            System.out.println("方法三:key = "+entry.getKey()+"--value="+entry.getValue());
        }
        //方法四,该方法比较低效
        for (Integer key : map.keySet()) {
            String value = map.get(key);
            System.out.println("Key = " + key + ", Value = " + value);
        }
map的源码和set的源码基本类似
hashtable是线程安全,key-value 都不能为空,初始化为11个

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5716814.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)