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); // }
public static void main(String[] args) { Listlist源码
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无参构造器验证
ArrayList1.初始化容量
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源码
List1.初始化空
public linkedList() { }2.添加元素
public boolean add(E e) { linkLast(e); return true; }
void linkLast(E e) { final Node3.再次添加元素 总结:arraylist改查效率比较高,linkedlist增删效率比较高 set源码l = last; final Node newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }
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总结:HashSet 无序复杂度都是O(1) ,TreeSet复杂度O(log(n))【TreeSet是有序的,而Dog类不是有序的,我们需要将Dog类实现Comparable接口】,元素是有序。linkedHashSet时间复杂度是O(1),插入的顺序进行输出。 hashmap循环[] 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; }
Mapmap的源码和set的源码基本类似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); }
hashtable是线程安全,key-value 都不能为空,初始化为11个
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)