单机获取不重复15位流水号的算法-自增多线程冲突

wangboak 发布于 2014/11/23 21:51
阅读 1K+
收藏 3

开发中,经常需要获取一些流水号,或称为ID,这些ID经常无业务意义,仅仅是为了区分不同的实体或数据库中的记录。UUID提供了一种非常好的策略,考虑到了时间、机器ID(涉及CPU编号、网卡MAC等等物理信息)、随机值等信息,能生成在时空中“唯一”的字符串,需要注意,此唯一并不是绝对唯一,如果不考虑主动造假和作弊,目前能保证唯一。

在具体的开发中,UUID生成的UUID字符串过长,不太适合业务场景。而且如果是单机场景,还有点浪费。

我在开发过程中,使用了这样一种方法,来解决唯一ID的生成,又不至于太长。1)获取系统当前时间的毫秒值,系统一般返回的是Long型,将该值转换成16进制,目的是为了缩小生成结果字符串的长度。2)使用一个全局int变量,每次获取唯一ID时,该变量自增 1,并追加到第一步中的字符串后面。如果想保持获取到的字符串长度一致,可以补0字符串。

在上面所述的方案中,为了在单位时间内生成的唯一ID尽量多,将自增的int值转换成36进制(10位数字+26位字母),这样就使单位毫秒内生成的唯一ID数量在36的N次方个。N=打算生成多少位字符串。如果打算生成15位唯一ID,则当前时间会占去11位(16进制的字符形式),4位36进制字符,大约在160万个。也就是说,1 毫秒内生成 160万个字符不重复。

此种方案主要的核心是:如何保证全局共享的int自增数值在多线程环境下,能原子性的自增呢?答案是 同步控制 或者 AtomicInteger类。

简单的实现和测试类如下:

思路如下:1)main方法中启动了20个线程,每个线程循环获取100个字符串,并将字符串放置入 全局的hashSet中,最后打印出hashSet的长度。如果恰好是2000,则证明没问题,否则存在问题;2)生成15位字符串的方法是 获取当前时间毫秒值,并转换成16进制,然后使用AtomicInteger的自增并获取的原子方法。最后补全位数15位。

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;
 
/**
 * 
 * @version v1.0
 * @createDate Nov 22, 2014 10:34:22 PM
 * @since JDK 1.7
 **/
public class ThreadSnUtil implements Runnable {
 
    private final static String str62 = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    private static final AtomicInteger ATOM_INT = new AtomicInteger(0);
 
    public static final HashSet<String> hash = new HashSet<>(2000);
 
    @Override
    public void run() {
        for (int i = 0; i < 100; i++) {
            hash.add(create15());
        }
    }
 
    /**
     * 创建一个15位的字符串,一毫秒内不超过1600000个内不重复:36*36*36*36。
     * @return
     */
    public final static String create15() {
        StringBuilder sb = new StringBuilder(15);
        sb.append(Long.toHexString(System.currentTimeMillis()));
        String str = longTo36(ATOM_INT.incrementAndGet());
        if (str.length() == 1) {
            sb.append("000").append(str);
        } else if (str.length() == 2) {
            sb.append("00").append(str);
        } else if (str.length() == 3) {
            sb.append("0").append(str);
        } else {
            sb.append(str);
        }
        return sb.toString();
    }
 
    /**
     * long型10进制转换成36进制的字符串形式
     * @param num
     * @return
     */
    public static final String longTo36(long num) {
        return ten2Any(num, 36);
    }
 
    /**
     * 10进制转任意进制
     * @param num Long型值
     * @param base 转换的进制
     * @return 任意进制的字符形式
     */
    private static final String ten2Any(long num, int base) {
        StringBuilder sb = new StringBuilder(7);
        while (num != 0) {
            sb.append(str62.charAt((int) (num % base)));
            num /= base;
        }
        return sb.reverse().toString();
    }
 
    public static void main(String[] args) throws InterruptedException {
        List<Thread> list = new ArrayList<>();
        for (int i = 0; i < 20; i++) {
            Thread t = new Thread(new ThreadSnUtil());
            t.start();
            list.add(t);
        }
        for (Thread thread : list) {
            thread.join();
        }
        System.out.println("总和:" + ThreadSnUtil.hash.size());
    }
}




可是问题来了:每次我测试的时候,结果都是 小于2000.....  郁闷坏了!!!可是我又没发现问题在哪?

各位oscer们:看出问题来了给我请给我留言,否则我会疯的。我不想使用同步关键字方法来约束。

加载中
1
优雅先生
优雅先生

因为HashSet不是线程安全的集合类,所以多线程环境下调用hash.add(create15());是难以预测的。你可以改成用ConcurrentHashMap或者多线程顺序执行试试看,我帮你改成ConcurrentHashMap测试下是OK的,如下:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * 
 * @version v1.0
 * @createDate Nov 22, 2014 10:34:22 PM
 * @since JDK 1.7
 **/
public class ThreadSnUtil implements Runnable {

	private static final String str62 = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
	private static final AtomicInteger ATOM_INT = new AtomicInteger(0);
	private static final String EMPTY_STRING = "";
	private static final Map<String, String> ARRAY = new ConcurrentHashMap<String, String> ();

	@Override
	public void run() {
		for (int i = 0; i < 100; i++) {
			ARRAY.put(create15(), EMPTY_STRING);
		}
	}

	/**
	 * 创建一个15位的字符串,一毫秒内不超过1600000个内不重复:36*36*36*36。
	 * 
	 * @return
	 */
	public final static String create15() {
		StringBuilder sb = new StringBuilder(15);
		sb.append(Long.toHexString(System.currentTimeMillis()));
		String str = longTo36(ATOM_INT.incrementAndGet());
		if (str.length() == 1) {
			sb.append("000").append(str);
		} else if (str.length() == 2) {
			sb.append("00").append(str);
		} else if (str.length() == 3) {
			sb.append("0").append(str);
		} else {
			sb.append(str);
		}
		return sb.toString();
	}

	/**
	 * long型10进制转换成36进制的字符串形式
	 * 
	 * @param num
	 * @return
	 */
	public static final String longTo36(long num) {
		return ten2Any(num, 36);
	}

	/**
	 * 10进制转任意进制
	 * 
	 * @param num
	 *            Long型值
	 * @param base
	 *            转换的进制
	 * @return 任意进制的字符形式
	 */
	private static final String ten2Any(long num, int base) {
		StringBuilder sb = new StringBuilder(7);
		while (num != 0) {
			sb.append(str62.charAt((int) (num % base)));
			num /= base;
		}
		return sb.reverse().toString();
	}

	public static void main(String[] args) throws InterruptedException {
		List<Thread> list = new ArrayList<Thread>();
		for (int i = 0; i < 20; i++) {
			Thread t = new Thread(new ThreadSnUtil());
			t.start();
			list.add(t);
		}
		for (Thread thread : list) {
			thread.join();
		}
		System.out.println("总和:" + ThreadSnUtil.ARRAY.size());
	}
}




返回顶部
顶部