设计模式-单例模式

单例模式(Singleton Pattern):确保某一个类只有一个实例,而且自行实例化并向整个系统提供这个实例,这个类称为单例类,它提供全局访问的方法。单例模式是一种对象创建型模式。

单例模式有三个要点:一是某个类只能有一个实例;二是它必须自行创建这个实例;三是它必须自行向整个系统提供这个实例。
单例模式是结构最简单的设计模式一,在它的核心结构中只包含一个被称为单例类的特殊类。单例模式结构如图所示:

单例模式结构图中只包含一个单例角色:

  • Singleton(单例):在单例类的内部实现只生成一个实例,同时它提供一个静态的getInstance()工厂方法,让客户可以访问它的唯一实例;为了防止在外部对其实例化,将其构造函数设计为私有;在单例类内部定义了一个Singleton类型的静态对象,作为外部共享的唯一实例。

实现

饿汉单例类

饿汉式单例类是实现起来最简单的单例类,饿汉式单例类结构图如图所示:

从图中可以看出,由于在定义静态变量的时候实例化单例类,因此在类加载的时候就已经创建了单例对象,代码如下所示:

public class EagerSingleton {
    private static final EagerSingleton EAGER_SINGLETON = new EagerSingleton();

    private EagerSingleton() {

    }

    public static EagerSingleton getInstance() {
        return EAGER_SINGLETON;
    }
}

懒汉单例模式

除了饿汉式单例,还有一种经典的懒汉式单例。懒汉式单例类结构图如图所示:

从图中可以看出,懒汉式单例在第一次调用getInstance()方法时实例化,在类加载时并不自行实例化,这种技术又称为延迟加载(Lazy Load)技术,即需要的时候再加载实例,为了避免多个线程同时调用getInstance()方法,我们可以使用关键字synchronized,代码如下所示:

public class LazySingleton1 {
    private static LazySingleton1 instance = null;

    private LazySingleton1() {
    }

    synchronized public static LazySingleton1 getInstance() {
        if (instance == null) {
            instance = new LazySingleton1();
        }
        return instance;
    }
}

该懒汉式单例类在getInstance()方法前面增加了关键字synchronized进行线程锁,以处理多个线程同时访问的问题。但是,上述代码虽然解决了线程安全问题,但是每次调用getInstance()时都需要进行线程锁定判断,在多线程高并发访问环境中,将会导致系统性能大大降低。如何既解决线程安全问题又不影响系统性能呢?我们继续对懒汉式单例进行改进。事实上,我们无须对整个getInstance()方法进行锁定,只需对其中的代码instance = new LazySingleton();进行锁定即可。因此getInstance()方法可以进行如下改进:

public static LazySingleton getInstance() {   
    if (instance == null) {  
        synchronized (LazySingleton.class) {  
            instance = new LazySingleton();   
        }  
    }  
    return instance;   
} 

问题貌似得以解决,事实并非如此。如果使用以上代码来实现单例,还是会存在单例对象不唯一。原因如下:假如在某一瞬间线程A和线程B都在调用getInstance()方法,此时instance对象为null值,均能通过instance == null的判断。由于实现了synchronized加锁机制,线程A进入synchronized锁定的代码中执行实例创建代码,线程B处于排队等待状态,必须等待线程A执行完毕后才可以进入synchronized锁定代码。但当A执行完毕时,线程B并不知道实例已经创建,将继续创建新的实例,导致产生多个单例对象,违背单例模式的设计思想,因此需要进行进一步改进,在synchronized中再进行一次(instance == null)判断,这种方式称为双重检查锁定(Double-Check Locking)。使用双重检查锁定实现的懒汉式单例类完整代码如下所示:

class LazySingleton {   
    private volatile static LazySingleton instance = null;   
  
    private LazySingleton() { }   
  
    public static LazySingleton getInstance() {   
        //第一重判断  
        if (instance == null) {  
            //锁定代码块  
            synchronized (LazySingleton.class) {  
                //第二重判断  
                if (instance == null) {  
                    instance = new LazySingleton(); //创建单例实例  
                }  
            }  
        }  
        return instance;   
    }  
}  

需要注意的是,如果使用双重检查锁定来实现懒汉式单例类,需要在静态成员变量instance之前增加修饰符volatile,被volatile修饰的成员变量可以确保多个线程都能够正确处理,且该代码只能在JDK 1.5及以上版本中才能正确执行。由于volatile关键字会屏蔽Java虚拟机所做的一些代码优化,可能会导致系统运行效率降低,因此即使使用双重检查锁定来实现单例模式也不是一种完美的实现方式。

懒汉和饿汉的比较

饿汉式单例类在类被加载时就将自己实例化,它的优点在于无须考虑多线程访问问题,可以确保实例的唯一性;从调用速度和反应时间角度来讲,由于单例对象一开始就得以创建,因此要优于懒汉式单例。但是无论系统在运行时是否需要使用该单例对象,由于在类加载时该对象就需要创建,因此从资源利用效率角度来讲,饿汉式单例不及懒汉式单例,而且在系统加载时由于需要创建饿汉式单例对象,加载时间可能会比较长。
懒汉式单例类在第一次使用时创建,无须一直占用系统资源,实现了延迟加载,但是必须处理好多个线程同时访问的问题,特别是当单例类作为资源控制器,在实例化时必然涉及资源初始化,而资源初始化很有可能耗费大量时间,这意味着出现多线程同时首次引用此类的机率变得较大,需要通过双重检查锁定等机制进行控制,这将导致系统性能受到一定影响。

静态内部类实现法

饿汉式单例类不能实现延迟加载,不管将来用不用始终占据内存;懒汉式单例类线程安全控制烦琐,而且性能受影响。可见,无论是饿汉式单例还是懒汉式单例都存在这样那样的问题,有没有一种方法,能够将两种单例的缺点都克服,而将两者的优点合二为一呢?答案是:Yes!下面我们来学习这种更好的被称之为Initialization Demand Holder (IoDH)的技术。
在IoDH中,我们在单例类中增加一个静态(static)内部类,在该内部类中创建单例对象,再将该单例对象通过getInstance()方法返回给外部使用,实现代码如下所示:

class Singleton {  
    private Singleton() {  
    }  
      
    private static class HolderClass {  
            private final static Singleton instance = new Singleton();  
    }  
      
    public static Singleton getInstance() {  
        return HolderClass.instance;  
    }  
      
    public static void main(String args[]) {  
        Singleton s1, s2;   
            s1 = Singleton.getInstance();  
        s2 = Singleton.getInstance();  
        System.out.println(s1==s2);  
    }  
}  

编译并运行上述代码,运行结果为:true,即创建的单例对象s1和s2为同一对象。由于静态单例对象没有作为Singleton的成员变量直接实例化,因此类加载时不会实例化Singleton,第一次调用getInstance()时将加载内部类HolderClass,在该内部类中定义了一个static类型的变量instance,此时会首先初始化这个成员变量,由Java虚拟机来保证其线程安全性,确保该成员变量只能初始化一次。由于getInstance()方法没有任何线程锁定,因此其性能不会造成任何影响。

通过使用IoDH,我们既可以实现延迟加载,又可以保证线程安全,不影响系统性能,不失为一种最好的Java语言单例模式实现方式(其缺点是与编程语言本身的特性相关,很多面向对象语言不支持IoDH)。

总结

单例模式作为一种目标明确、结构简单、理解容易的设计模式,在软件开发中使用频率相当高,在很多应用软件和框架中都得以广泛应用。

主要优点

单例模式的主要优点如下:

  1. 单例模式提供了对唯一实例的受控访问。因为单例类封装了它的唯一实例,所以它可以严格控制客户怎样以及何时访问它。
  2. 由于在系统内存中只存在一个对象,因此可以节约系统资源,对于一些需要频繁创建和销毁的对象单例模式无疑可以提高系统的性能。
  3. 允许可变数目的实例。基于单例模式我们可以进行扩展,使用与单例控制相似的方法来获得指定个数的对象实例,既节省系统资源,又解决了单例单例对象共享过多有损性能的问题。

主要缺点

单例模式的主要缺点如下:

  1. 由于单例模式中没有抽象层,因此单例类的扩展有很大的困难。
  2. 单例类的职责过重,在一定程度上违背了“单一职责原则”。因为单例类既充当了工厂角色,提供了工厂方法,同时又充当了产品角色,包含一些业务方法,将产品的创建和产品的本身的功能融合到一起。

适用场景

在以下情况下可以考虑使用单例模式:

  1. 系统只需要一个实例对象,如系统要求提供一个唯一的序列号生成器或资源管理器,或者需要考虑资源消耗太大而只允许创建一个对象。
  2. 客户调用类的单个实例只允许使用一个公共访问点,除了该公共访问点,不能通过其他途径访问该实例。

实现

相关代码Github地址
文章参考-刘伟

2017/3/13 posted in  Java
 

剑指Offer-合并两个排序的链表

输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

非递归实现

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode head = new ListNode(0);
        ListNode p = head;
        boolean isFirst = true;
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                p.next = list1;
                list1 = list1.next;
            }else{
                p.next = list2;
                list2 = list2.next;
            }
            p = p.next;
        }
        if(list1 != null){
            p.next = list1;
        }
        if(list2 != null){
            p.next = list2;
        }
        return head.next;
    }
    
}

递归实现

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        
        ListNode head = null;
        
        if(list1.val < list2.val){
            head = list1;
            head.next = Merge(list1.next, list2);
        }else{
            head = list2;
            head.next = Merge(list1, list2.next);
        }
        return head;
    }
    
}
2017/3/13 posted in  算法-数据结构
 

设计模式-抽象工厂模式

提供一个创建一系列相关或相互依赖对象的接口,而无须指定它们具体的类。抽象工厂模式又称为Kit模式,它是一种对象创建型模式。

抽象工厂模式为创建一组对象提供了一种解决方案。与工厂方法模式相比,抽象工厂模式中的具体工厂不只是创建一种产品,它负责创建一族产品。
在抽象工厂模式中,每一个具体工厂都提供了多个工厂方法用于产生多种不同类型的产品,这些产品构成了一个产品族。

角色

在抽象工厂模式结构图中包含如下几个角色:

  1. AbstractFactory(抽象工厂):它声明了一组用于创建一族产品的方法,每一个方法对应一种产品。
  2. ConcreteFactory(具体工厂):它实现了在抽象工厂中声明的创建产品的方法,生成一组具体产品,这些产品构成了一个产品族,每一个产品都位于某个产品等级结构中。
  3. AbstractProduct(抽象产品):它为每种产品声明接口,在抽象产品中声明了产品所具有的业务方法。
  4. ConcreteProduct(具体产品):它定义具体工厂生产的具体产品对象,实现抽象产品接口中声明的业务方法。

抽象工厂模式结构如图所示:

实现

在抽象工厂中声明了多个工厂方法,用于创建不同类型的产品,抽象工厂可以是接口,也可以是抽象类或者具体类,其典型代码如下所示:

public abstract class AbstractFactory {
    /**
     * 生产A产品的具体实例
     * 
     * @return
     */
    public abstract ProductA createProductA();

    /**
     * 生产B产品的具体实例
     * 
     * @return
     */
    public abstract ProductB createProductB();
}

具体工厂实现了抽象工厂,每一个具体的工厂方法可以返回一个特定的产品对象,而同一个具体工厂所创建的产品对象构成了一个产品族。对于每一个具体工厂类,其典型代码如下所示:

public class ConcreteFactoryOne extends AbstractFactory {
    @Override
    public ProductA createProductA() {
        return new ConcreteProductA();
    }

    @Override
    public ProductB createProductB() {
        return new ConcreteProductB();
    }
}

public class ConcreteFactoryTwo extends AbstractFactory {
    @Override
    public ProductA createProductA() {
        return new ConcreteProductA2();
    }

    @Override
    public ProductB createProductB() {
        return new ConcreteProductB2();
    }
}

总结

抽象工厂模式是工厂方法模式的进一步延伸,由于它提供了功能更为强大的工厂类并且具备较好的可扩展性,在软件开发中得以广泛应用,尤其是在一些框架和API类库的设计中,例如在Java语言的AWT(抽象窗口工具包)中就使用了抽象工厂模式,它使用抽象工厂模式来实现在不同的操作系统中应用程序呈现与所在操作系统一致的外观界面。抽象工厂模式也是在软件开发中最常用的设计模式之一。

主要优点

抽象工厂模式的主要优点如下:

  1. 抽象工厂模式隔离了具体类的生成,使得客户并不需要知道什么被创建。由于这种隔离,更换一个具体工厂就变得相对容易,所有的具体工厂都实现了抽象工厂中定义的那些公共接口,因此只需改变具体工厂的实例,就可以在某种程度上改变整个软件系统的行为。
  2. 当一个产品族中的多个对象被设计成一起工作时,它能够保证客户端始终只使用同一个产品族中的对象。
  3. 增加新的产品族很方便,无须修改已有系统,符合“开闭原则”。

主要缺点

增加新的产品等级结构麻烦,需要对原有系统进行较大的修改,甚至需要修改抽象层代码,这显然会带来较大的不便,违背了“开闭原则”。

适用场景

在以下情况下可以考虑使用抽象工厂模式:

  1. 一个系统不应当依赖于产品类实例如何被创建、组合和表达的细节,这对于所有类型的工厂模式都是很重要的,用户无须关心对象的创建过程,将对象的创建和使用解耦。
  2. 系统中有多于一个的产品族,而每次只使用其中某一产品族。可以通过配置文件等方式来使得用户可以动态改变产品族,也可以很方便地增加新的产品族。
  3. 属于同一个产品族的产品将在一起使用,这一约束必须在系统的设计中体现出来。同一个产品族中的产品可以是没有任何关系的对象,但是它们都具有一些共同的约束,如同一操作系统下的按钮和文本框,按钮与文本框之间没有直接关系,但它们都是属于某一操作系统的,此时具有一个共同的约束条件:操作系统的类型。
  4. 产品等级结构稳定,设计完成之后,不会向系统中增加新的产品等级结构或者删除已有的产品等级结构。

实现

相关代码Github地址
文章参考-刘伟

2017/3/12 posted in  Java
 

设计模式-工厂方法模式

工厂方法模式(Factory Method Pattern):定义一个用于创建对象的接口,让子类决定将哪一个类实例化。工厂方法模式让一个类的实例化延迟到其子类。工厂方法模式又简称为工厂模式(Factory Pattern),又可称作虚拟构造器模式(Virtual Constructor Pattern)或多态工厂模式(Polymorphic Factory Pattern)。工厂方法模式是一种类创建型模式。

在简单工厂模式中只提供一个工厂类,该工厂类处于对产品类进行实例化的中心位置,它需要知道每一个产品对象的创建细节,并决定何时实例化哪一个产品类。简单工厂模式最大的缺点是当有新产品要加入到系统中时,必须修改工厂类,需要在其中加入必要的业务逻辑,这违背了“开闭原则”。此外,在简单工厂模式中,所有的产品都由同一个工厂创建,工厂类职责较重,业务逻辑较为复杂,具体产品与工厂类之间的耦合度高,严重影响了系统的灵活性和扩展性,而工厂方法模式则可以很好地解决这一问题。
在工厂方法模式中,我们不再提供一个统一的工厂类来创建所有的产品对象,而是针对不同的产品提供不同的工厂,系统提供一个与产品等级结构对应的工厂等级结构

工厂方法模式中的角色

工厂方法模式提供一个抽象工厂接口来声明抽象工厂方法,而由其子类来具体实现工厂方法,创建具体的产品对象。
在工厂方法模式结构图中包含如下几个角色:

  1. Product(抽象产品):它是定义产品的接口,是工厂方法模式所创建对象的超类型,也就是产品对象的公共父类。
  2. ConcreteProduct(具体产品):它实现了抽象产品接口,某种类型的具体产品由专门的具体工厂创建,具体工厂和具体产品之间一一对应。
  3. Factory(抽象工厂):在抽象工厂类中,声明了工厂方法(Factory Method),用于返回一个产品。抽象工厂是工厂方法模式的核心,所有创建对象的工厂类都必须实现该接口。
  4. ConcreteFactory(具体工厂):它是抽象工厂类的子类,实现了抽象工厂中定义的工厂方法,并可由客户端调用,返回一个具体产品类的实例。

工厂方法模式结构如图2所示:

实现

与简单工厂模式相比,工厂方法模式最重要的区别是引入了抽象工厂角色,抽象工厂可以是接口,也可以是抽象类或者具体类,其典型代码如下所示:

public interface AbstarctFactory {
    public Product createProduct();
}

在抽象工厂中声明了工厂方法但并未实现工厂方法,具体产品对象的创建由其子类负责,客户端针对抽象工厂编程,可在运行时再指定具体工厂类,具体工厂类实现了工厂方法,不同的具体工厂可以创建不同的具体产品,其典型代码如下所示:

public class ConcreteFactoryA implements AbstarctFactory {
    @Override
    public Product createProduct() {
        return new ConcreteProductA();
    }
}

在实际使用时,具体工厂类在实现工厂方法时除了创建具体产品对象之外,还可以负责产品对象的初始化工作以及一些资源和环境配置工作,例如连接数据库、创建文件等。
在客户端代码中,只需关心工厂类即可,不同的具体工厂可以创建不同的产品,典型的客户端类代码片段如下所示:

AbstractFactory factory;  
factory = new ConcreteFactoryA(); //可通过配置文件实现  
Product product;  
product = factory.createProduct();  

可以通过配置文件来存储具体工厂类ConcreteFactory的类名,更换新的具体工厂时无须修改源代码,系统扩展更为方便。

总结

工厂方法模式是简单工厂模式的延伸,它继承了简单工厂模式的优点,同时还弥补了简单工厂模式的不足。工厂方法模式是使用频率最高的设计模式之一,是很多开源框架和API类库的核心模式。

主要优点

工厂方法模式的主要优点如下:

  1. 在工厂方法模式中,工厂方法用来创建客户所需要的产品,同时还向客户隐藏了哪种具体产品类将被实例化这一细节,用户只需要关心所需产品对应的工厂,无须关心创建细节,甚至无须知道具体产品类的类名。
  2. 基于工厂角色和产品角色的多态性设计是工厂方法模式的关键。它能够让工厂可以自主确定创建何种产品对象,而如何创建这个对象的细节则完全封装在具体工厂内部。工厂方法模式之所以又被称为多态工厂模式,就正是因为所有的具体工厂类都具有同一抽象父类。
  3. 使用工厂方法模式的另一个优点是在系统中加入新产品时,无须修改抽象工厂和抽象产品提供的接口,无须修改客户端,也无须修改其他的具体工厂和具体产品,而只要添加一个具体工厂和具体产品就可以了,这样,系统的可扩展性也就变得非常好,完全符合“开闭原则”。

主要缺点

工厂方法模式的主要缺点如下:

  1. 在添加新产品时,需要编写新的具体产品类,而且还要提供与之对应的具体工厂类,系统中类的个数将成对增加,在一定程度上增加了系统的复杂度,有更多的类需要编译和运行,会给系统带来一些额外的开销。
  2. 由于考虑到系统的可扩展性,需要引入抽象层,在客户端代码中均使用抽象层进行定义,增加了系统的抽象性和理解难度,且在实现时可能需要用到DOM、反射等技术,增加了系统的实现难度。

适用场景

在以下情况下可以考虑使用工厂方法模式:

  1. 客户端不知道它所需要的对象的类。在工厂方法模式中,客户端不需要知道具体产品类的类名,只需要知道所对应的工厂即可,具体的产品对象由具体工厂类创建,可将具体工厂类的类名存储在配置文件或数据库中。
  2. 抽象工厂类通过其子类来指定创建哪个对象。在工厂方法模式中,对于抽象工厂类只需要提供一个创建产品的接口,而由其子类来确定具体要创建的对象,利用面向对象的多态性和里氏代换原则,在程序运行时,子类对象将覆盖父类对象,从而使得系统更容易扩展。

实现

相关代码Github地址
文章参考-刘伟

2017/3/12 posted in  Java
 

剑指Offer-二进制中1的个数

输入一个整数n,输出该数二进制表示中1的个数。其中负数用补码表示。

思路

  • 方案一:

    将(n&1)可以知道n的最后一位是不是1,然后依次将n不断向右移1位,直到n为0。

public class Solution {
    public int NumberOf1(int n) {
        int count = 0;
        while(n != 0){
            if( (n & 1) == 1){
                count++;
            }
            /*
            *注意,这里是>>>
            *>>为最高位填补符号位,负数会发生错误
            *>>>为最高位填写0
            */
            n = n >>> 1;
        }
        return count;
    }
}
  • 方案二:

    将一个整数减一,都是把最右边的1变成0,如果它的右边还有0的话,所有的0都变成1,而它的左边的所有位都保持不变。若我们将n和n-1做与运算,相当于把它最右边的1变成0。那么,一个整数的二进制表示中有多少个1,就可以进行多少次这样的操作。

public class Solution {
    public int NumberOf1(int n) {
        int count = 0;
        while(n != 0){
            count++;
            n = n & (n-1);
        }
        return count;
    }
}
2017/3/12 posted in  算法-数据结构