ConcurrentHashMap能完全替代HashTable吗?

回答:hash table虽然性能上不如ConcurrentHashMap,但并不能完全被取代,两者的迭代器的一致性不同的,hash table的迭代器是强一致性的,而concurrenthashmap是弱一致的。 ConcurrentHashMap的get,clear,iterator 都是弱一致性的。 Doug Lea 也将这个判断留给用户自己决定是否使用ConcurrentHashMap。

 

如何显示海量用户网站的积分排名?

某海量用户网站,用户拥有积分,积分可能会在使用过程中随时更新。现在要为该网站设计一种算法,在每次用户登录时显示其当前积分排名。用户最大规模为2亿;积分为非负整数,且小于100万。

回答1:用map做的,key是分数,value是人数。查排名的失火遍历map里比他积分大key取出value的sum一下。

更多方法参考:http://www.ituring.com.cn/article/1169

CopyOnWriteArrayList类set方法疑惑?

在淘宝内网有位同事提了一个很好的问题,大家能否帮忙解答下?

在CopyOnWriteArrayList类的set方法中有一段setArray(elements)代码,实际上这段代码并未对elements做任何改动,实现的volatile语意并不对CopyOnWriteArrayList实例产生任何影响,为什么还是要保留这行语句?见以下代码红体部分:

    /** The array, accessed only via getArray/setArray. */
    private volatile transient Object[] array;

    /**
     * Replaces the element at the specified position in this list with the
     * specified element.
     *
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E set(int index, E element) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            E oldValue = get(elements, index);

            if (oldValue != element) {
                int len = elements.length;
                Object[] newElements = Arrays.copyOf(elements, len);
                newElements[index] = element;
                setArray(newElements);
            } else {
                // Not quite a no-op; ensures volatile write semantics
                setArray(elements);
            }
            return oldValue;
        } finally {
            lock.unlock();
        }
    }

    /**
     * Sets the array.
     */
    final void setArray(Object[] a) {
        array = a;
    }

    /**
     * Gets the array.  Non-private so as to also be accessible
     * from CopyOnWriteArraySet class.
     */
    final Object[] getArray() {
        return array;
    }

这个问题在concurrency-interest邮件列表里也有人讨论:

http://cs.oswego.edu/pipermail/concurrency-interest/2010-February/006886.html

Java Fork Join框架 (二) 简介

原文 http://gee.cs.oswego.edu/dl/papers/fj.pdf

作者:Doug Lea
译者:Alex

Fork/Join并行方式是获取良好的并行计算性能的一种最简单同时也是最有效的设计技术。Fork/Join并行算法是我们所熟悉的分治算法的并行版本,典型的用法如下:

Result solve(Problem problem) {
	if (problem is small) 
		directly solve problem
		else {
			split problem into independent parts
			fork new subtasks to solve each part
			join all subtasks
			compose result from subresults
		}
}

Fork操作将会启动一个新的并行fork/join子任务。Join操作会一直等待直到所有的子任务都结束。Fork/Join算法,如同其他分治算法一样,总是会递归的、反复的划分子任务,直到这些子任务可以用足够简单的、短小的顺序方法来执行。

一些相关的编程技术和实例在Java并发编程——设计原则与模式 第二版 [7] 4.4章节中已经讨论过。这篇论文将讨论FJTask的设计(第2节)、实现(第3节)以及性能(第4节),它是一个支持并行编程方式的Java框架。FJTask 作为util.concurrent软件包的一部分,目前可以在http://gee.cs.oswego.edu.获取到。

Java Fork Join 框架

原文地址 作者:Doug Lea  译者:Alex

1. 摘要
2. 简介
3. 设计
4. 实现
5. 性能
6. 结论
7. 致谢
8. 参考文献

Java Fork Join框架 (一) 摘要

原文 http://gee.cs.oswego.edu/dl/papers/fj.pdf

作者:Doug Lea  译者:Alex  校对:方腾飞

这篇论文描述了Fork/Join框架的设计、实现以及性能,这个框架通过(递归的)把问题划分为子任务,然后并行的执行这些子任务,等所有的子任务都结束的时候,再合并最终结果的这种方式来支持并行计算编程。总体的设计参考了为Cilk(校注1:英特尔Cilk 语言)设计的work-stealing框架。就设计层面来说主要是围绕如何高效的去构建和管理任务队列以及工作线程来展开的。性能测试的数据显示良好的并行计算程序将会提升大部分应用,同时也暗示了一些潜在的可以提升的空间。

校注1:Cilk是英特尔Cilk 语言。英特尔C++ 编辑器的新功能 Cilk 语言扩展技术,为 C/C++ 语言增加了细粒度任务支持,使其为新的和现有的软件增加并行性来充分发掘多处理器能力变得更加容易。

 

同步和Java内存模型

原文:http://gee.cs.oswego.edu/dl/cpj/jmm.html

作者:Doug Lea 译者:程晓明,萧欢,杜建雄  校对:方腾飞,丁一,欧振聪

目录

  1. 引言
  2. 原子性
  3. 可见性
  4. 有序性
  5. Volatile

同步和Java内存模型 (二)原子性

原文:http://gee.cs.oswego.edu/dl/cpj/jmm.html 第二章

作者:Doug Lea 译者:程晓明  校对:方腾飞

除了long型字段和double型字段外,java内存模型确保访问任意类型字段所对应的内存单元都是原子的。这包括引用其它对象的引用类型的字段。此外,volatile long 和volatile double也具有原子性 。(虽然java内存模型不保证non-volatile long 和 non-volatile double的原子性,当然它们在某些场合也具有原子性。)(译注:non-volatile long在64位JVM,OS,CPU下具有原子性)

当在一个表达式中使用一个non-long或者non-double型字段时,原子性可以确保你将获得这个字段的初始值或者某个线程对这个字段写入之后的值;但不会是两个或更多线程在同一时间对这个字段写入之后产生混乱的结果值(即原子性可以确保,获取到的结果值所对应的所有bit位,全部都是由单个线程写入的)。但是,如下面(译注:指可见性章节)将要看到的,原子性不能确保你获得的是任意线程写入之后的最新值。 因此,原子性保证通常对并发程序设计的影响很小。

Read more

同步和Java内存模型(四)有序性

原文链接: http://gee.cs.oswego.edu/dl/cpj/jmm.html

作者:Doug lea 译者:杜建雄  校对者:欧振聪,方腾飞

有序性 

有序性规则表现在以下两种场景: 线程内和线程间

  •  从某个线程的角度看方法的执行,指令会按照一种叫“串行”(as-if-serial)的方式执行,此种方式已经应用于顺序编程语言。
  •  这个线程“观察”到其他线程并发地执行非同步的代码时,任何代码都有可能交叉执行。唯一起作用的约束是:对于同步方法,同步块以及volatile字段的操作仍维持相对有序。

 
Read more

Java内存模型FAQ(十三)为什么我需要关注java内存模型

原文:http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html#conclusion
译者:Alex

为什么你需要关注java内存模型?并发程序的bug非常难找。它们经常不会在测试中发生,而是直到你的程序运行在高负荷的情况下才发生,非常难于重现和跟踪。你需要花费更多的努力提前保证你的程序是正确同步的。这不容易,但是它比调试一个没有正确同步的程序要容易的多。

Read more

Java内存模型FAQ(十二)如果我需要写一个VM,我需要做些什么

原文:http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html#vmwriters
译者:Alex

参见:http://gee.cs.oswego.edu/dl/jmm/cookbook.html (译文参见:JMM Cookbook)
Read more

Java内存模型FAQ(十一)新的内存模型是否修复了双重锁检查问题?

原文:http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html#dcl
译者:Alex

臭名昭著的双重锁检查(也叫多线程单例模式)是一个骗人的把戏,它用来支持lazy初始化,同时避免过度使用同步。在非常早的JVM中,同步非常慢,开发人员非常希望删掉它。 Read more

Java内存模型FAQ(十)volatile是干什么用的

原文:http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html#volatile
译者:Alex

Volatile字段是用于线程间通讯的特殊字段。每次读volatile字段都会看到其它线程写入该字段的最新值;实际上,程序员之所以要定义volatile字段是因为在某些情况下由于缓存和重排序所看到的陈旧的变量值是不可接受的。编译器和运行时禁止在寄存器里面分配它们。它们还必须保证,在它们写好之后,它们被从缓冲区刷新到主存中,因此,它们立即能够对其他线程可见。相同地,在读取一个volatile字段之前,缓冲区必须失效,因为值是存在于主存中而不是本地处理器缓冲区。在重排序访问volatile变量的时候还有其他的限制。 Read more

Java内存模型FAQ(九)在新的Java内存模型中,final字段是如何工作的

原文:http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html 第九章
译者:Alex

一个对象的final字段值是在它的构造方法里面设置的。假设对象被正确的构造了,一旦对象被构造,在构造方法里面设置给final字段的的值在没有同步的情况下对所有其他的线程都会可见。另外,引用这些final字段的对象或数组都将会看到final字段的最新值。 Read more

Java内存模型FAQ(八)Final字段如何改变它们的值

原文:http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html 第八章

译者:Alex

我们可以通过分析String类的实现具体细节来展示一个final变量是如何可以改变的。

String对象包含了三个字段:一个character数组,一个数组的offset和一个length。实现String类的基本原理为:它不仅仅拥有character数组,而且为了避免多余的对象分配和拷贝,多个String和StringBuffer对象都会共享相同的character数组。因此,String.substring()方法能够通过改变length和offset,而共享原始的character数组来创建一个新的String。对一个String来说,这些字段都是final型的字段。

String s1 = "/usr/tmp";
String s2 = s1.substring(4); 

字符串s2的offset的值为4,length的值为4。但是,在旧的内存模型下,对其他线程来说,看到offset拥有默认的值0是可能的,而且,稍后一点时间会看到正确的值4,好像字符串的值从“/usr”变成了“/tmp”一样。

旧的Java内存模型允许这些行为,部分JVM已经展现出这样的行为了。在新的Java内存模型里面,这些是非法的。

原文

How can final fields appear to change their values?

One of the best examples of how final fields’ values can be seen to change involves one particular implementation of the String class.

String can be implemented as an object with three fields — a character array, an offset into that array, and a length. The rationale for implementing String this way, instead of having only the character array, is that it lets multiple String and StringBufferobjects share the same character array and avoid additional object allocation and copying. So, for example, the method String.substring() can be implemented by creating a new string which shares the same character array with the original String and merely differs in the length and offset fields. For a String, these fields are all final fields.

String s1 = "/usr/tmp";
String s2 = s1.substring(4); 

The string s2 will have an offset of 4 and a length of 4. But, under the old model, it was possible for another thread to see the offset as having the default value of 0, and then later see the correct value of 4, it will appear as if the string “/usr” changes to “/tmp”.

The original Java Memory Model allowed this behavior; several JVMs have exhibited this behavior. The new Java Memory Model makes this illegal.

return top