Java ArrayList工作原理及实现

概述

以数组实现。节约空间,但数组有容量限制。超出限制时会增加50%容量,用System.arraycopy()复制到新的数组,因此最好能给出数组大小的预估值。默认第一次插入元素时,创建大小为10的数组。

基本优势

按数组下标访问元素get(i) set(i, e)的性能很高。

直接在数组末尾加入元素add(e)的性能也高。

基本劣势

如果按下表插入、删除元素add(i, e) remove(i) remove(e),则要用System.arraycopy()来移动部分受影响的元素,性能就变差了。

ArrayList<String> list = new ArrayList<String>();
list.add("语文: 99");
list.add("数学: 98");
list.add("英语: 100");
list.remove(0);

add操作:直接将数组的内容置位

remove操作:删除index为0的节点,并将后面的元素移到0处。

add函数

add函数:将元素放到末尾

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

ensureCapacityInternal自动扩容机制的核心

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
 
    ensureExplicitCapacity(minCapacity);
}
 
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
 
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
 
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 扩展为原来的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果扩为1.5倍还不满足需求,直接扩为需求值
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}
  • 当增加数据的时候,如果ArrayList的大小已经不满足需求时,那么就将数组变为原长度的1.5倍
  • 之后的操作就是把老的数组拷到新的数组里面

set和get函数

  • 先做index范围检查,看是不是越界了
  • 然后做赋值或访问操作

remove函数

public E remove(int index) {
    rangeCheck(index);
 
    modCount++;
    E oldValue = elementData(index);
 
    int numMoved = size - index - 1;
    if (numMoved > 0)
        // 把后面的往前移
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 把最后的置null
    elementData[--size] = null; // clear to let GC do its work
 
    return oldValue;
}
  • 删除要删的元素
  • 将排在删除元素后面的往前移

Reference

http://www.importnew.com/18865.html

2016/4/2 posted in  Java

Java序列化

序列化:一种将对象以一连串的字节描述的过程
反序列化:一种将这些字节重建成一个对象的过程

序列化的应用场景

  • 当你想把的内存中的对象保存到一个文件中或者数据库中时候(数据持久化);
  • 当你想用套接字在网络上传送对象的时候;
  • 当你想通过RMI传输对象的时候; Java RMI 支持存储于不同地址空间的程序级对象之间彼此进行通信,实现远程对象之间的无缝远程调用

实现序列化

将需要序列化的类实现Serializable接口就可以了,Serializable接口中没有任何方法,可以理解为一个标记,即表明这个类可以序列化.

序列化例子

FileOutputStream fos = new FileOutputStream("serialize.obj");  
ObjectOutputStream oos = new ObjectOutputStream(fos);  
Serialize serialize = new Serialize();  
oos.writeObject(serialize);  
oos.flush();  
oos.close();
fos.close();  

反序列化例子

FileInputStream fis = new FileInputStream("serialize.obj");  
ObjectInputStream ois = new ObjectInputStream(fis);  
serialize = (Serialize) ois.readObject();  
ois.close();  
fis.close();  

相关注意事项

  • 序列化时,只对对象的状态进行保存,而不管对象的方法;
  • 当一个父类实现序列化,子类自动实现序列化,不需要显式实现Serializable接口;
  • 当一个对象的实例变量引用其他对象,序列化该对象时也把引用对象进行序列化;
  • 并非所有的对象都可以序列化,至于为什么不可以,有很多原因了,比如:
    1. 安全方面的原因,比如一个对象拥有privatepublicfield,对于一个要传输的对象,比如写到文件,或者进行rmi传输 等等,在序列化进行传输的过程中,这个对象的private等域是不受保护的。
    2. 资源分配方面的原因,比如socketthread类,如果可以序列化,进行传输或者保存,也无法对他们进行重新的资源分配,而且也是没有必要这样实现。

序列化前和序列化后的对象的关系

序列化时深复制,反序列化还原后的对象地址与原来的不同。

不同的原因:
通过序列化操作,我们可以实现对任何可Serializable对象的”深度复制(deep copy)"——这意味着我们复制的是整个对象网,而不仅仅是基本对象及其引用。对于同一流的对象,他们的地址是相同,说明他们是同一个对象,但是与其他流的对象地址却不相同。也就说,只要将对象序列化到单一流中,就可以恢复出与我们写出时一样的对象网,而且只要在同一流中,对象都是同一个。

破坏单例模式

单例是要求一个JVM中只有一个类对象的, 而现在通过反序列化,一个新的对象克隆了出来.

package com.serialize;

import java.io.Serializable;

public class SerSingleton implements Serializable
{
    private static final long serialVersionUID = 1L;
    
    String name;
    
    private SerSingleton()
    {
        System.out.println("Singleton is create");
        name="SerSingleton";
    }
    
    private static SerSingleton instance = new SerSingleton();
    
    public static SerSingleton getInstance()
    {
        return instance;
    }
    
    public static void createString()
    {
        System.out.println("createString in Singleton");
    }
}

@Test
public void test() throws IOException, ClassNotFoundException
{
    SerSingleton s1= null;
    SerSingleton s = SerSingleton.getInstance();
    
    FileOutputStream fos = new FileOutputStream("SerSingleton.obj");
    ObjectOutputStream oos = new ObjectOutputStream(fos);
    oos.writeObject(s);
    oos.flush();
    oos.close();
    
    FileInputStream fis = new FileInputStream("SerSingleton.obj");
    ObjectInputStream ois = new ObjectInputStream(fis);
    s1 = (SerSingleton)ois.readObject();
    System.out.println(s==s1);
}
    
----------
private Object readResolve()  
{  
    return instance;  
}  

输出false

说明测试代码中的ss1指向了不同的实例,在反序列化后,生成多个对象实例。

加上第二部分代码:这样当JVM从内存中反序列化地"组装"一个新对象时,就会自动调用这个readResolve方法来返回我们指定好的对象了, 单例规则也就得到了保证.

序列化ID

序列化IDEclipse下提供了两种生成策略,一个是固定的1L,一个是随机生成一个不重复的long类型数据(实际上是使用JDK工具生成),在这里有一个建议,如果没有特殊需求,就是用默认的1L就可以,这样可以确保代码一致时反序列化成功。这也可能是造成序列化和反序列化失败的原因,因为不同的序列化id之间不能进行序列化和反序列化。

静态变量能否序列化

序列化会忽略静态变量,即序列化不保存静态变量的状态。静态成员属于类级别的,所以不能序列化。即 序列化的是对象的状态不是类的状态。这里的不能序列化的意思,是序列化信息中不包含这个静态成员域。transient后的变量也不能序列化。

transient小结

  1. 一旦变量被transient修饰,变量将不再是对象持久化的一部分,该变量内容在序列化后无法获得访问。

  2. transient关键字只能修饰变量,而不能修饰方法和类。注意,本地变量是不能被transient关键字修饰的。变量如果是用户自定义类变量,则该类需要实现Serializable接口。

  3. transient关键字修饰的变量不再能被序列化,一个静态变量不管是否被transient修饰,均不能被序列化。

注意:

Java对象序列化不仅保留一个对象的数据,而且递归保存对象引用的每个对象的数据

对象的序列化可以通过实现两种接口来实现,若实现的是Serializable接口,则所有的序列化将会自动进行,若实现的是Externalizable接口,则没有任何东西可以自动序列化,需要在writeExternal方法中进行手工指定所要序列化的变量,这与是否被transient修饰无关

总结

  1. 当父类继承Serializable接口时,所有子类都可以被序列化。
  2. 子类实现了Serializable接口,父类没有,父类中的属性不能被序列化(不报错,数据不会丢失)但是在子类中的属性仍能正确序列化
  3. 如果序列化的属性是对象,则这个对象也必须实现Serializable接口,否则会报错。
  4. 在反序列化时,如果对象的属性有修改或删减,则修改的部分属性会丢失,但不会报错。
  5. 在反序列化时,如果serialVersionUID被序列化,则反序列化时会失败
  6. 当一个对象的实例变量引用其他对象,序列化改对象时,也把引用对象进行序列化
  7. statictransient后的变量不能被序列化
2016/3/31 posted in  Java

Java传值还是传引用

2016/3/31 posted in  Java

Java 基础之`final`、`static`、`transient`

一、关于final

根据程序上下文环境,Java关键字fina这是无法改变的或者终态的含义,它可以修饰非抽象类、非抽象类成员方法和变量。你可能出于两种理解而需要阻止改变:设计或效率。

final类不能被继承,没有子类,final类中的方法默认是final的。

final方法不能被子类的方法覆盖,但可以被继承。

final成员变量表示常量,只能被赋值一次,赋值后值不再改变。

final不能用于修饰构造方法。

注意:父类的private成员方法是不能被子类方法覆盖的,因此private类型的方法默认是final类型的。

1、final

final类不能被继承,因此final类的成员方法没有机会被覆盖,默认都是final的。在设计类时候,如果这个类不需要有子类,类的实现细节不允许改变,并且确信这个类不会再被扩展,那么就设计为final

2、final方法

如果一个类不允许其子类覆盖某个方法,则可以把这个方法声明为final方法

使用final方法的原因有二:

第一、把方法锁定,防止任何继承类修改它的意义和实现。

第二、高效。编译器在遇到调用final方法时候会转入内嵌机制,大大提高执行效率。

3、final变量(常量)

final修饰的成员变量表示常量,值一旦给定就无法改变

final修饰的变量有三种:静态变量、实例变量和局部变量,分别表示三种类型的常量。

另外,final变量定义的时候,可以先声明,而不给初值,这中变量也称为final空白,无论什么情况,编译器都确保空白final在使用之前必须被初始化。但是,final空白在final关键字final的使用上提供了更大的灵活性,为此,一个类中的final数据成员就可以实现依对象而有所不同,却有保持其恒定不变的特征。

4、final参数

当函数参数为final类型时,你可以读取使用该参数,但是无法改变该参数的值(网上最流行的说法)。

特例

public class Test {
    public static void main(String[] args)  {
        MyClass myClass = new MyClass();
        StringBuffer buffer = new StringBuffer("hello");
        myClass.changeValue(buffer);
        System.out.println(buffer.toString());
    }
}
 
class MyClass {
 
    void changeValue(final StringBuffer buffer) {
        buffer.append("world");
    }
}

====> helloworld

Once a final variable has been assigned, it always contains the same value. If a final variable holds a reference to an object, then the state of the object may be changed by operations on the object, but the variable will always refer to the same object.

如果一个被final关键字修饰的变量A指向一个对象B的引用,那么这个变量A的状态可能会随着B的改变而改变,但A一直都指向B

在上例中,变量Abuffer)指向一个对象BStringBuffer)的引用,对象BStringBuffer)的值改变了,但是他的内存地址没有改变。

final StringBuffer a = new StringBuffer("Hello");
a = new StringBuffer("World"); //this wont compile

二、关于static

static表示全局或者静态的意思,用来修饰成员变量和成员方法,也可以形成静态static代码块,但是Java语言中没有全局变量的概念。

1、static变量

按照是否静态的对类成员变量进行分类可分两种:一种是被static修饰的变量,叫静态变量或类变量;另一种是没有被static修饰的变量,叫实例变量。两者的区别是:

对于静态变量在内存中只有一个拷贝(节省内存), JVM 只为静态分配一次内存,在加载类的过程中完成静态变量的内存分配,可用类名直接访问(方便),当然也可以通过对象来访问(但是这是不推荐的)。

对于实例变量,每创建一个实例,就会为实例变量分配一次内存,实例变量可以在内存中有多个拷贝,互不影响(灵活)。

public修饰的static成员变量和成员方法本质是全局变量和全局方法,当声明其他类的对象时,不生成static变量的副本,而是类的所有实例共享同一个static变量。

static变量前可以有private修饰,表示这个变量可以在类的静态代码块中,或者类的其他静态成员方法中使用,但是不能在其他类中通过类名来直接引用,这一点很重要。实际上你需要搞明白,private是访问权限限定,static表示不要实例化就可以使用,这样就容易理解多了。static前面加上其它访问权限关键字的效果也以此类推。

2、static方法

静态方法可以直接通过类名调用,任何的实例也都可以调用,因此静态方法中不能用thissuper关键字,不能直接访问所属类的实例变量和实例方法(就是不带static的成员变量和成员成员方法),只能访问所属类的静态成员变量和成员方法。因为实例成员与特定的对象关联!

因为static方法独立于任何实例,因此static方法必须被实现,而不能是抽象的abstract

3、static代码块

static代码块也叫静态代码块,是在类中独立于类成员的static语句块,可以有多个,位置可以随便放,它不在任何的方法体内,JVM加载类时会执行这些静态的代码块,如果static代码块有多个,JVM将按照它们在类中出现的先后顺序依次执行它们,每个代码块只会被执行一次

4、staticfinal一块用表示什么

staticfinal用来修饰成员变量和成员方法,可简单理解为“全局常量”

对于变量,表示一旦给值就不可修改,并且通过类名可以访问。

对于方法,表示不可覆盖,并且可以通过类名直接访问。

特别要注意一个问题:

对于被staticfinal修饰过的实例常量,实例本身不能再改变了,但对于一些容器类型(比如,ArrayListHashMap)的实例变量,不可以改变容器变量本身,但可以修改容器中存放的对象,这一点在编程中用到很多。

5、静态内部类

这里简单介绍下,什么是静态内部类。

简单的说内部类前加static就是静态内部类了,上代码:

public class Outer { 
    static int x =1;
    static class Nest {
        void print(){
            System.out.println("Nest "+x);
        }
    }
    public static void main(String[] args){
        Outer.Nest nest = new Outer.Nest();
        nest.print();
    }
}

当内部类是static时,意味着:

  • 要创建静态内部类的对象,并不需要其外部类的对象;

  • 不能够从静态内部类的对象中访问外部类的非静态成员;

与普通的内部类的一个区别:在非静态内部类中不可以声明静态成员,只有将某个内部类修饰为静态类,然后才能够在这个类中定义静态的成员变量与成员方法。

6、静态导包

所谓静态导入包:import static com. ... . ClassName.*这样写可以导入相关类里面的所有静态方法,或者也可以直接静态导入具体到静态方法名。

这样写的好处是,引用静态方法不用在前面加上类名.

需要注意两点:

  • 提防含糊不清的命名static成员。例如,如果你对Integer类和Long类执行了静态导入,引用MAX_VALUE将导致一个编译器错误,因为IntegerLong都有一个MAX_VALUE常量,并且Java不会知道你在引用哪个MAX_VALUE

  • 方法名的命名尽量明确,让看代码的人看到名称就知道这个方法是干嘛用的,不然静态导入会让代码变的难读。

附:

对象的初始化顺序:

  • 首先执行父类静态的内容,父类静态的内容执行完毕后,
  • 接着去执行子类的静态的内容,当子类的静态内容执行完毕之后,
  • 再去看父类有没有非静态代码块,如果有就执行父类的非静态代码块,
  • 父类的非静态代码块执行完毕,接着执行父类的构造方法
  • 父类的构造方法执行完毕之后,它接着去看子类有没有非静态代码块,如果有就执行子类的非静态代码块。
  • 子类的非静态代码块执行完毕再去执行子类的构造方法

总之一句话,静态代码块内容先执行,接着执行父类非静态代码块和构造方法,然后执行子类非静态代码块和构造方法

**注意: 子类的构造方法,不管这个构造方法带不带参数,默认的它都会先去寻找父类的不带参数的构造方法**。如果父类没有不带参数的构造方法,那么子类必须用super关键子来调用父类带参数的构造方法,否则编译不能通过。

三、transient

java 的transient关键字为我们提供了便利,你只需要实现Serilizable接口,将不需要序列化的属性前添加关键字transient,序列化对象的时候,这个属性就不会序列化到指定的目的地中。

  • 一旦变量被transient修饰,变量将不再是对象持久化的一部分,该变量内容在序列化后无法获得访问。

  • transient关键字只能修饰变量,而不能修饰方法和类。注意,本地变量是不能被transient关键字修饰的。变量如果是用户自定义类变量,则该类需要实现Serializable接口。

  • transient关键字修饰的变量不再能被序列化,一个静态变量不管是否被transient修饰,均不能被序列化。

2016/3/25 posted in  Java

Java内存访问重排序的研究

public class PossibleReordering {
    static int x = 0, y = 0;
    static int a = 0, b = 0;
    
    public static void main(String[] args) throws InterruptedException {
        Thread one = new Thread(new Runnable() {
            public void run() {
                a = 1;
                x = b;
            }
        });
    
        Thread other = new Thread(new Runnable() {
            public void run() {
                b = 1;
                y = a;
            }
        });
        one.start();other.start();
        one.join();other.join();
        System.out.println(“(” + x + “,” + y + “)”);
    }
}

这段代码的执行结果也可能是(0,0),因为,在实际运行时,代码指令可能并不是严格按照代码语句顺序执行的。

得到(0,0)结果的语句执行过程:

a=1x=b这两个语句的赋值操作的顺序被颠倒了,或者说,发生了指令“重排序(reording)

大多数现代微处理器都会采用将指令乱序执行的方法,在条件允许的情况下,直接运行当前有能力立即执行的后续指令,避免获取下一条指令所需数据时造成的等待,通过乱序执行的技术,处理器可以大大提高执行效率。

as-if-serial语义

所有的动作都可以为了优化而被重排序,但是必须保证它们重排序后的结果和程序代码本身的应有结果是一致的。

int a = 1;
int b = 2;
int c = a + b;

将上面的代码编译成Java字节码或生成机器指令,可视为展开成了以下动作:

1. 对a赋值1
2. 对b赋值2
3. 取a的值
4. 取b的值
5. 将取到两个值相加后存入c

在上面5个动作中,动作1可能会和动作2、4重排序,动作2可能会和动作1、3重排序,动作3可能会和动作2、4重排序,动作4可能会和动作1、3重排序。但动作1动作3、5不能重排序。动作2动作4、5不能重排序。因为它们之间存在数据依赖关系,一旦重排,as-if-serial语义便无法保证

内存访问重排序与内存可见性

计算机系统中,为了尽可能地避免处理器访问主内存的时间开销,处理器大多会利用缓存(cache)以提高性能。

在这种模型下会存在一个现象,即缓存中的数据与主内存的数据并不是实时同步的,各CPU(或CPU核心)间缓存的数据并不是实时同步的。从程序的视角来看,就是同一个时间点,各个线程所看到的共享变量的值可能是不一致的。

内存访问重排序与Java内存模型

根据Java内存模型中的规定,可以总结出以下几条happens-before规则。happens-before的前后两个操作不会被重排序且后者对前者的内存可见。

  • 程序次序法则:线程中的每个动作Ahappens-before于该线程中的每一个动作B,其中,在程序中,所有的动作B都能出现在动作A之后。
  • 监视器锁法则:对一个监视器锁的解锁happens-before于每一个后续对同一监视器锁的加锁。
  • volatile变量法则:对volatile域的写入操作happens-before于每一个后续对同一个域的读写操作。
  • 线程启动法则:在一个线程里,对Thread.start()的调用会happens-before于每个启动线程的动作。
  • 线程终结法则:线程中的任何动作都happens-before于其他线程检测到这个线程已经终结、或者从Thread.join()调用中成功返回,或Thread.isAlive()返回false
  • 中断法则:一个线程调用另一个线程的interrupt happens-before于被中断的线程发现中断。
  • 终结法则:一个对象的构造函数的结束happens-before于这个对象finalizer的开始。
  • 传递性:如果A happens-beforeB,且B happens-beforeC,则A happens-beforeC

Reference

http://tech.meituan.com/java-memory-reordering.html

2016/3/25 posted in  Java