不变设计模式(immutable pattern)
1 定义
这些对象共享相同对象的引用，为此，在对象构造好之后，不允许改变共享对象的内容
2 例子
在jdk中String被设计为不可变类,一旦生成一个String对象,它的所有属性就不会被变,任何方法要么返回这个对象本身的原
始状态,要么抛弃原来的字符串返回一个新字符串,而绝对不会返回被修改了的字符串对象.
StringBuffer是可变类
3 如何设计不可变类
不变类，即类中的方法和属性不能被外界修改，包括其子类
1.类本身声明为final,可以保证它本身的状态不会被子类扩展方法所改变，即没有子类。
2.类的所有成员变量都是final的,保证它在构造后不会被重新赋值.而且类所有属性是private的,只提供getter访问.
3.类的能传入的参数是Immutable的，且返回的属性也是不可变的.
如果方法返回的属性是基本类型，则在类中将该属性声明为final即可。
如果是引用类型，该属性的final只能保证引用类型的引用地址不可变，无法保证外界对该引用类型内容的修改，所以一般返回该引用类型的一份拷贝。
注意：在将可变类封装到不变类的时候要特别小心.因为你传入的引用在外面是可以被修改的.所以即使你不变类本身不能去改变属性，但属性有一个外部引用.可以在外面修改。
4 优缺点
1）不变类优点：
多个线程共享一个不变类的实例时,这个实例的状态不会发生改变.事实上它没有地方让你去改变.所以多线程共享一个不变类的实例时，不需要进行临界区保护（即同步）。
2）不变类缺点：不灵活
5 应用
5.1设计一个缓存
例子：设计一个单例，属性HashMap已被赋值，外部只能使用属性HashMap的值，不能对其进行修改,所以只返回HashMap中的值，不返回该HashMap的引用地址。
/**
* Fuction:
* 输入参数是不可变的，返回的HashMap不是hm，即其引用地址，每次返回它的副本，所以外界也无法修改hm
* @author E-mail:yangzhonglive@gmail.com
* @version 2013-10-7 下午9:57:16
* @since 1.0
*/
public final class ImmutableBuffer {
private volatile static ImmutableBuffer uniqueInstance=null;
private final HashMap hm=new HashMap();
private ImmutableBuffer(){
//设置缓存值
hm.put("a", 1);
hm.put("b", 2);
}
public static ImmutableBuffer getInstance(){
if(uniqueInstance==null){
synchronized (ImmutableBuffer.class){ //note we only synchronize the first time through!
if(uniqueInstance == null) //once in the block,check again and if still null, create an instance
uniqueInstance=new ImmutableBuffer();
}//end synchronized
}//end if
return uniqueInstance;
}//end geInstance()
public HashMap getHashMap(){
HashMap copy=new HashMap();
copy.putAll(hm);
return copy;
}//end getHashMap()
/**
* @param args
*/
public static void main(String[] args) {
ImmutableBuffer ib=ImmutableBuffer.getInstance();
//尝试改变缓存值
HashMap hm=ib.getHashMap();
hm.put("c", 3);
//测试是否改变
HashMap hm2=ib.getHashMap();
Set entry=hm2.entrySet();
Iterator it=entry.iterator();
while(it.hasNext()){
Map.Entry me=(Map.Entry)it.next();
//获得关键字getKey()，获得值getValue()
System.out.println(me.getKey()+":"+me.getValue());
}//end while
}//end main()
}
5.2 实现Immutable的FIFO队列，要求时间复杂度为O(1)
The Queue class represents an immutable first-in-first-out (FIFO) queue of objects. Use two @see PersistentStack to implement the persistent queue.
Every element is pushed on the incoming stack once, popped off the incoming stack once, pushed on the outgoing stack once and popped off the outgoing stack once. enqueue(E) is O(1). Dequeuing is on average O(1), though it is * O(n) for a single case which
only few happens when reverse incoming stack elements into outgoing stack.
不变队列实现用2个不变栈来实现，不变栈类如下
/**
* Implement an persistent stack, here persistent stacks with the same tail can
* share state, saving on memory.
*
* @author E-mail:yangzhonglive@gmail.com
* @version 2013-10-12
* @since 1.0
*/
public final class PersistentStack<E> implements Iterable<E> {
// ----------------------------------------------------
// ---private properties
// ----------------------------------------------------
/**
* The head value of this persistent stack.
*/
private final E head;
/**
* The head of this persistent stack, and it is the tail reference of the
* stack which add element into this persistent stack
*/
private final PersistentStack<E> tail;
/**
* The number of elements in this persistent stack.
*/
private final int size;
// ----------------------------------------------------
// ---constructor
// ----------------------------------------------------
/**
* Initial an empty persistent stack.
*/
public PersistentStack() {
this.head = null;
this.tail = null;
this.size = 0;
}
/**
* Construct a new persistent stack based on the input persistent stack.
*
* @param head
* @param tail
*/
public PersistentStack(E head, PersistentStack<E> tail) {
this.head = head;
this.tail = tail;
this.size = tail.size() + 1;
}
// ----------------------------------------------------
// ---API
// ----------------------------------------------------
/**
* Returns true if this persistent stack contains no elements.
*
* @return
*/
public boolean isEmpty() {
return (size == 0);
} // end isEmpty()
/**
* Retrieves, but does not remove, the head of this persistent stack. This
* method throws an exception if this persistent stack is empty.
*
* @return
*/
public E peek() {
if (isEmpty())
throw new NoSuchElementException();
else
return head;
} // end peek()
/**
* Inserts the specified element into this persistent stack
*
* @param value
* @return
*/
public PersistentStack<E> push(E e) {
return new PersistentStack<E>(e, this);
} // end push()
/**
* Removes the head of this persistent stack. This method throws an
* exception if this persistent stack is empty.
*
* @return
* @throws java.util.NoSuchElementException
*/
public PersistentStack<E> pop() {
if (isEmpty())
throw new NoSuchElementException();
else
return tail;
} // end pop()
/**
* Returns the number of elements in this persistent stack.
*
* @return
*/
public int size() {
return this.size;
}
/**
* A stack is essentially a “backwards” queue, so reverse this stack
* elements to a new stack for remove element from queue.
*
* @return
* @see PersistentQueue#dequeue()
*/
public PersistentStack<E> reverse() {
if (this.isEmpty())
return new PersistentStack<E>();
else {
PersistentStack<E> stack = new PersistentStack<E>();
for (E e : this) {
stack = stack.push(e);
}// end for
return stack;
}// end else
}// end reverse()
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
private PersistentStack<E> stack = PersistentStack.this;
@Override
public boolean hasNext() {
return !stack.isEmpty();
}
@Override
public E next() {
if (!hasNext())
throw new NoSuchElementException();
E e = stack.head;
stack = stack.tail;
return e;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
};
}
} // end class PersistentStack
不变队列实现
/**
* The Queue class represents an immutable first-in-first-out (FIFO) queue of
* objects. Use two @see PersistentStack to implement the persistent queue.
* Every element is pushed on the incoming stack once, popped off the incoming
* stack once, pushed on the outgoing stack once and popped off the outgoing
* stack once. enqueue(E) is O(1). Dequeuing is on average O(1), though it is
* O(n) for a single case which only few happens when reverse incoming stack
* elements into outgoing stack.
*
* @author E-mail:yangzhonglive@gmail.com
* @version 2013-10-12
* @since 1.0
* @param <E>
*/
public class PersistentQueue<E> {
// ----------------------------------------------------
// ---private properties
// ----------------------------------------------------
/**
* Add elements in this stack when add elements in this persistent queue
*/
private final PersistentStack<E> incoming;
/**
* Remove elements from this stack when remove elements from this persistent
* queue
*/
private final PersistentStack<E> outgoing;
// ----------------------------------------------------
// ---constructor
// ----------------------------------------------------
/**
* requires default constructor. Initial an empty persistent queue.
*/
public PersistentQueue() {
incoming = new PersistentStack<E>();
outgoing = new PersistentStack<E>();
}
/**
* Construct a new persistent queue based on the input persistent queue.
*
* @param outgoing
* @param incoming
*/
public PersistentQueue(PersistentStack<E> outgoing,
PersistentStack<E> incoming) {
this.outgoing = outgoing;
this.incoming = incoming;
}
// ----------------------------------------------------
// ---API
// ----------------------------------------------------
/**
* Returns the queue that adds an item into the tail of this queue without
* modifying this queue.
*
* <pre>
* e.g.
* When this queue represents the queue (2, 1, 2, 2, 6) and we enqueue the value 4 into this queue,
* this method returns a new queue (2, 1, 2, 2, 6, 4)
* and this object still represents the queue (2, 1, 2, 2, 6) .
* </pre>
*
* If the element e is null, throws IllegalArgumentException.
*
* <pre>
* How to enqueue works:
* add element into incoming stack.
* </pre>
*
* @param e
* @return
* @throws IllegalArgumentException
*/
public PersistentQueue<E> enqueue(E e) {
return new PersistentQueue<>(outgoing, incoming.push(e));
}
/**
* Returns the queue that removes the object at the head of this queue
* without modifying this queue.
*
* <pre>
* e.g.
* When this queue represents the queue (7, 1, 3, 3, 5, 1) ,
* this method returns a new queue (1, 3, 3, 5, 1)
* and this object still represents the queue (7, 1, 3, 3, 5, 1) .
* </pre>
*
* If this queue is empty, throws java.util.NoSuchElementException.
*
* <pre>
* How to dequeue works:
* 1) if both incoming stack and outgoing stack are empty, just throws java.util.NoSuchElementException.
* 2) if only the outgoing stack is empty, we first reverse the incoming stack as outgoing stack @see PersistentStack#reverse(), then pop from outgoing stack.
* 3) if outgoing stack is not empty, just pop from outgoing stack.
* </pre>
*
* @return
* @throws java.util.NoSuchElementException
*/
public PersistentQueue<E> dequeue() {
if (isEmpty()) // both empty
throw new NoSuchElementException();
else if (outgoing.isEmpty()) { // only the outgoing stack is empty
PersistentStack<E> stack = incoming.reverse().pop();
return new PersistentQueue<E>(stack, new PersistentStack<E>());
}// end if
else
// both are not empty
return new PersistentQueue<>(outgoing.pop(), incoming);
} // end dequeue()
/**
* Looks at the object which is the head of this queue without removing it
* from the queue.
*
* <pre>
* e.g.
* When this queue represents the queue (7, 1, 3, 3, 5, 1),
* this method returns 7 and this object still represents the queue (7, 1, 3, 3, 5, 1)
* </pre>
*
* If the queue is empty, throws java.util.NoSuchElementException.
*
* @return
* @throws java.util.NoSuchElementException
*/
public E peek() {
if (isEmpty()) // both empty
throw new NoSuchElementException();
else if (outgoing.isEmpty()) { // outgoing is empty, but incoming not
// empty
return incoming.reverse().peek();
}// end if
else
return outgoing.peek();
}// end peek()
/**
* Returns the number of objects in this queue.
*
* @return
*/
public int size() {
return (outgoing.size() + incoming.size());
} // end size()
/**
* Returns true if this persistent stack contains no elements.
*
* @return
*/
public boolean isEmpty() {
return (size() == 0);
}// end isEmpty()
}// end class
在前面写的基础上实现添加一个队列的函数
public ExamImmutableQueue<E> append(ExamImmutableQueue<E> queue){
ExamImmutableQueue<E> temp=queue;
ExamImmutableQueue<E> result=this;
if(!queue.isEmpty()){
for(int i=0;i<queue.size;i++){
q.add(temp.peek());
temp=temp.dequeue();
}//end for
}//end if
return result;
} //end append()
参考文献：
Immutability in C# Part Four: An Immutable Queue
Immutability in C# Part Two: A Simple Immutable Stack
Making an immutable queue with guaranteed constant time operations