
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) {
List
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无参构造器验证
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 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循环
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条)