{"id":2086,"date":"2017-08-05T16:41:10","date_gmt":"2017-08-05T08:41:10","guid":{"rendered":"https:\/\/ai.zhousir.top\/?p=2086"},"modified":"2026-08-18T12:09:37","modified_gmt":"2026-08-18T04:09:37","slug":"concurrenthashmap%e4%b8%8ecas","status":"publish","type":"post","link":"https:\/\/ai.zhousir.top\/?p=2086","title":{"rendered":"ConcurrentHashMap\u4e0eCAS"},"content":{"rendered":"
\n

CAS<\/strong>\uff08Compare and Swap\uff09\u548c ConcurrentHashMap<\/code> \u7ecf\u5e38\u7ed1\u5728\u4e00\u8d77\u95ee\uff1a\u4e00\u4e2a\u662f\u786c\u4ef6\u7ea7\u7684\u65e0\u9501\u66f4\u65b0\uff0c\u4e00\u4e2a\u662f\u5e76\u53d1 Map \u600e\u4e48\u65e2\u7ebf\u7a0b\u5b89\u5168\u53c8\u6bd4\u6574\u8868\u9501\u66f4\u5feb\u3002<\/p>\n

JDK 5 \u4e4b\u524d\u540c\u6b65\u51e0\u4e4e\u5168\u9760 synchronized<\/code>\uff1a\u7ade\u4e89\u65f6\u4e0a\u4e0b\u6587\u5207\u6362\u591a\u3001\u6301\u9501\u4f1a\u628a\u522b\u4eba\u6302\u8d77\u3001\u8fd8\u53ef\u80fd\u4f18\u5148\u7ea7\u5012\u7f6e\u3002volatile<\/code> \u80fd\u4fdd\u8bc1\u53ef\u89c1\u6027\uff0c\u4f46\u4e0d\u4fdd\u8bc1\u590d\u5408\u64cd\u4f5c\u7684\u539f\u5b50\u6027\uff0c\u6240\u4ee5\u8fd8\u662f\u8981\u56de\u5230\u300c\u9501\u300d\u2014\u2014\u53ea\u4e0d\u8fc7\u4e50\u89c2\u9501\u7528\u7684\u662f CAS\uff0c\u800c\u4e0d\u662f\u72ec\u5360\u3002<\/p>\n

\u4e00\u3001\u60b2\u89c2\u9501\u3001\u4e50\u89c2\u9501\u4e0e CAS<\/h2>\n\n\n\n\n\n\n
\u7c7b\u578b<\/th>\n\u505a\u6cd5<\/th>\n\u5178\u578b<\/th>\n<\/tr>\n<\/thead>\n
\u60b2\u89c2 \/ \u72ec\u5360<\/td>\n\u5148\u62a2\u9501\uff0c\u522b\u4eba\u7b49\u7740\uff1b\u6301\u9501\u7ebf\u7a0b\u4e0d\u653e\uff0c\u5176\u4f59\u5168\u6302\u8d77<\/td>\nsynchronized<\/code><\/td>\n<\/tr>\n
\u4e50\u89c2<\/td>\n\u5148\u5047\u8bbe\u6ca1\u51b2\u7a81\u505a\u5b8c\uff0c\u5931\u8d25\u5c31\u91cd\u8bd5\u76f4\u5230\u6210\u529f<\/td>\nCAS \/ compareAndSet<\/code><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

CAS \u4e09\u4e2a\u64cd\u4f5c\u6570<\/h3>\n

\u5185\u5b58\u4f4d\u7f6e V\u3001\u9884\u671f\u539f\u503c A\u3001\u65b0\u503c B\u3002\u82e5 V \u4ecd\u7b49\u4e8e A\uff0c\u5904\u7406\u5668\u539f\u5b50\u5730\u628a V \u6539\u6210 B\uff1b\u5426\u5219\u4e0d\u52a8\u3002\u65e0\u8bba\u6210\u8d25\u90fd\u4f1a\u5e26\u56de\u8be5\u4f4d\u7f6e\u5f53\u524d\u503c\uff08\u6709\u7684\u53d8\u4f53\u53ea\u8fd4\u56de\u6210\u529f\u4e0e\u5426\uff09\u3002\u53e3\u8bed\u5c31\u662f\uff1a\u6211\u8ba4\u4e3a V \u91cc\u662f A\uff1b\u82e5\u662f\uff0c\u5c31\u5199\u6210 B\uff1b\u5426\u5219\u544a\u8bc9\u6211\u73b0\u5728\u662f\u591a\u5c11\u3002<\/p>\n

\u5e38\u89c1\u7528\u6cd5\uff1a\u4ece V \u8bfb\u51fa A\uff0c\u7b97\u51fa B\uff0c\u518d\u7528 CAS \u628a V \u4ece A \u6539\u6210 B\u3002\u522b\u4eba\u82e5\u5df2\u6539\u8fc7\uff0cCAS \u5931\u8d25\uff0c\u7b97\u6cd5\u91cd\u7b97\u5373\u53ef\u3002Intel \u4e0a\u5bf9\u5e94 cmpxchg<\/code>\uff1bJava \u65e9\u671f\u7528\u4e0d\u4e0a\u8fd9\u4e9b\u6307\u4ee4\uff0c\u6709\u4e86 JNI \u4e4b\u540e\uff0cDoug Lea \u7684 concurrent \u5305\u624d\u628a CAS \u5f53\u6210\u6574\u5305\u57fa\u77f3\u3002<\/p>\n

AtomicInteger \u600e\u4e48\u65e0\u9501 +1<\/h3>\n

\u6ca1\u6709\u9501\u65f6\uff0c\u503c\u672c\u8eab\u4ecd\u8981 volatile<\/code>\uff0c\u4fdd\u8bc1\u8bfb\u5230\u7684\u662f\u5171\u4eab\u7684\u6700\u65b0\u503c\uff1a<\/p>\n

private volatile int value;<\/code><\/pre>\n
public final int get() {\n\n        return value;\n\n    }<\/code><\/pre>\n
incrementAndGet<\/code> \u662f\u5178\u578b\u7684\u81ea\u65cb CAS\uff1a<\/p>\n
public final int incrementAndGet() {\n\n    for (;;) {\n\n        int current = get();\n\n        int next = current + 1;\n\n        if (compareAndSet(current, next))\n\n            return next;\n\n    }\n\n}<\/code><\/pre>\n
compareAndSet<\/code> \u7ecf JNI \u843d\u5230 CPU \u6307\u4ee4\uff1a<\/p>\n
public final boolean compareAndSet(int expect, int update) {\n\n    return unsafe.compareAndSwapInt(this, valueOffset, expect, update);\n\n    }<\/code><\/pre>\n
\u975e\u963b\u585e\u7b97\u6cd5\u7684\u8981\u6c42\u662f\uff1a\u4e00\u4e2a\u7ebf\u7a0b\u5931\u8d25\u6216\u6302\u8d77\uff0c\u4e0d\u8be5\u62d6\u6b7b\u522b\u7684\u7ebf\u7a0b\u3002compareAndSet<\/code> \u6b63\u662f\u7528\u786c\u4ef6\u66f4\u65b0 + \u51b2\u7a81\u68c0\u6d4b\uff0c\u4ee3\u66ff\u6574\u6bb5\u52a0\u9501\u3002<\/p>\n
\u4e8c\u3001ConcurrentHashMap \u7684\u8bbe\u8ba1<\/h2>\n
\u5e76\u53d1\u91cc ConcurrentHashMap<\/code> \u6bd4 Hashtable<\/code> \u548c Collections.synchronizedMap()<\/code> \u5199\u5e76\u53d1\u66f4\u597d\uff0c\u4ee3\u4ef7\u662f\u653e\u5bbd\u4e86\u8bfb\u7684\u5f3a\u4e00\u81f4\u6027\u3002<\/p>\n\n\n\n\n\n\n
\u7248\u672c<\/th>\n\u9501\u7b56\u7565<\/th>\n\u7ed3\u6784<\/th>\n<\/tr>\n<\/thead>\n
JDK 7<\/td>\n\u5206\u6bb5\u9501 Segment\uff1a\u540c\u6bb5\u624d\u7ade\u4e89\uff0c\u4e0d\u540c\u6bb5\u4e0d\u62a2<\/td>\n\u6bb5\u6570\u7ec4 + \u94fe\u8868<\/td>\n<\/tr>\n
JDK 8<\/td>\n\u53bb\u6389 Segment\uff0c\u8282\u70b9\u4e0a CAS \/ synchronized\uff0c\u6269\u5bb9\u4e5f\u9760 CAS<\/td>\n\u6570\u7ec4 + \u94fe\u8868 + \u7ea2\u9ed1\u6811\uff0c\u53e6\u6709 TreeBin\u3001Traverser \u7b49\u8f85\u52a9\u7c7b<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
\u4e09\u3001\u63a5\u53e3\u9650\u6d41\u91cc\u7684\u8ba1\u6570\u9677\u9631<\/h2>\n
\u7edf\u8ba1 URL \u8c03\u7528\u6b21\u6570\uff0c\u7b2c\u4e00\u53cd\u5e94\u5e38\u662f ConcurrentHashMap<String, Long><\/code>\u3002\u4e0b\u9762\u8fd9\u6bb5\u6ca1\u663e\u5f0f\u52a0\u9501\uff0c\u8f93\u51fa\u5374\u7ecf\u5e38\u5bf9\u4e0d\u4e0a\uff1a<\/p>\n
public class CounterDemo1 {\n\n    private final Map<String, Long> urlCounter = new ConcurrentHashMap<>();\n\n    \/\/\u63a5\u53e3\u8c03\u7528\u6b21\u6570+1\n\n    public long increase(String url) {\n\n        Long oldValue = urlCounter.get(url);\n\n        Long newValue = (oldValue == null) ? 1L : oldValue + 1;\n\n        urlCounter.put(url, newValue);\n\n        return newValue;\n\n    }\n\n    \/\/\u83b7\u53d6\u8c03\u7528\u6b21\u6570\n\n    public Long getCount(String url){\n\n        return urlCounter.get(url);\n\n    }\n\n    public static void main(String[] args) {\n\n        ExecutorService executor = Executors.newFixedThreadPool(10);\n\n        final CounterDemo1 counterDemo = new CounterDemo1();\n\n        int callTime = 100000;\n\n        final String url = \"http:\/\/localhost:8080\/hello\";\n\n        CountDownLatch countDownLatch = new CountDownLatch(callTime);\n\n        \/\/\u6a21\u62df\u5e76\u53d1\u60c5\u51b5\u4e0b\u7684\u63a5\u53e3\u8c03\u7528\u7edf\u8ba1\n\n        for(int i=0;i<callTime;i++){\n\n            executor.execute(new Runnable() {\n\n                @Override\n\n                public void run() {\n\n                    counterDemo.increase(url);\n\n                    countDownLatch.countDown();\n\n                }\n\n            });\n\n        }\n\n        try {\n\n            countDownLatch.await();\n\n        } catch (InterruptedException e) {\n\n            e.printStackTrace();\n\n        }\n\n        executor.shutdown();\n\n        \/\/\u7b49\u5f85\u6240\u6709\u7ebf\u7a0b\u7edf\u8ba1\u5b8c\u6210\u540e\u8f93\u51fa\u8c03\u7528\u6b21\u6570\n\n        System.out.println(\"\u8c03\u7528\u6b21\u6570\uff1a\"+counterDemo.getCount(url));\n\n    }\n\n}\n\nconsole output\uff1a\n\n\u8c03\u7528\u6b21\u6570\uff1a96526<\/code><\/pre>\n
ConcurrentHashMap \u4fdd\u8bc1\u7684\u662f \u5355\u4e2a<\/strong> get\/put\/delete \u539f\u5b50\uff0cincrease<\/code> \u5374\u662f get \u518d put \u7684\u7ec4\u5408\uff0c\u591a\u7ebf\u7a0b\u4f1a\u4e92\u76f8\u8986\u76d6\u3002\u7ed9\u6574\u4e2a\u65b9\u6cd5\u52a0\u9501\u53c8\u6d6a\u8d39\u4e86\u5e76\u53d1\u5bb9\u5668\u3002<\/p>\n
ConcurrentMap.replace(key, old, new)<\/code> \u624d\u662f\u539f\u5b50 CAS\uff1a<\/p>\n
\/**\n\n * Replaces the entry for a key only if currently mapped to a given value.\n\n * This is equivalent to\n\n *\n\n * if (map.containsKey(key) && Objects.equals(map.get(key), oldValue)) {\n\n *   map.put(key, newValue);\n\n *   return true;\n\n * } else\n\n *   return false;\n\n * }\n\n *\n\n * except that the action is performed atomically.\n\n *\/\n\nboolean replace(K key, V oldValue, V newValue);<\/code><\/pre>\n
\u65e7\u503c\u88ab\u522b\u4eba\u6539\u8fc7\uff0creplace \u5931\u8d25\uff1b\u5faa\u73af\u91cc\u62ff\u6700\u65b0\u503c\u518d\u8bd5\uff0c\u5c31\u80fd\u8ba1\u51c6\u3002\u9996\u6b21\u8fd8\u8981\u7528 putIfAbsent<\/code> \u505a\u521d\u59cb\u5316\uff1a<\/p>\n
public long increase2(String url) {\n\n        Long oldValue, newValue;\n\n        while (true) {\n\n            oldValue = urlCounter.get(url);\n\n            if (oldValue == null) {\n\n                newValue = 1l;\n\n                \/\/\u521d\u59cb\u5316\u6210\u529f\uff0c\u9000\u51fa\u5faa\u73af\n\n                if (urlCounter.putIfAbsent(url, 1l) == null)\n\n                    break;\n\n                \/\/\u5982\u679c\u521d\u59cb\u5316\u5931\u8d25\uff0c\u8bf4\u660e\u5176\u4ed6\u7ebf\u7a0b\u5df2\u7ecf\u521d\u59cb\u5316\u8fc7\u4e86\n\n            } else {\n\n                newValue = oldValue + 1;\n\n                \/\/+1\u6210\u529f\uff0c\u9000\u51fa\u5faa\u73af\n\n                if (urlCounter.replace(url, oldValue, newValue))\n\n                    break;\n\n                \/\/\u5982\u679c+1\u5931\u8d25\uff0c\u8bf4\u660e\u5176\u4ed6\u7ebf\u7a0b\u5df2\u7ecf\u4fee\u6539\u8fc7\u4e86\u65e7\u503c\n\n            }\n\n        }\n\n        return newValue;\n\n    }\n\nconsole output\uff1a\n\n\u8c03\u7528\u6b21\u6570\uff1a100000<\/code><\/pre>\n
\/** If the specified key is not already associated\n\n     * with a value, associate it with the given value.\n\n     * This is equivalent to\n\n     *\n\n     * if (!map.containsKey(key))\n\n     *   return map.put(key, value);\n\n     * else\n\n     *   return map.get(key);\n\n     * }<\/code><\/pre>\n
value \u4e0d\u80fd\u4e3a null\u3002\u4e5f\u53ef\u4ee5\u6362\u6210 AtomicLong<\/code> \/ AtomicLongMap<\/code>\uff0c\u8ba1\u6570\u66f4\u76f4\uff1a<\/p>\n
private AtomicLongMap<String> urlCounter3 = AtomicLongMap.create();\n\npublic long increase3(String url) {\n\n    long newValue = urlCounter3.incrementAndGet(url);\n\n    return newValue;\n\n}\n\npublic Long getCount3(String url) {\n\n    return urlCounter3.get(url);<\/code><\/pre>\n
java.util.concurrent.atomic<\/code> \u628a\u5e38\u7528\u7c7b\u578b\u5305\u4e00\u5c42\u539f\u5b50\u65b9\u6cd5\u3002\u53c2\u8003\uff1a\u4e50\u89c2\u9501\u4e0e\u60b2\u89c2\u9501<\/a>\u3001ConcurrentHashMap<\/a>\u3001CHM \u603b\u7ed3<\/a>\u3001\u5e76\u53d1\u5b9e\u8df5<\/a>\u3002<\/p>\n
\n
\u4e00\u53e5\u8bdd\u603b\u7ed3\uff1aCAS \u7528\u300c\u6bd4\u8f83\u518d\u4ea4\u6362\u300d\u5728\u786c\u4ef6\u4e0a\u5b8c\u6210\u65e0\u9501\u66f4\u65b0\uff1bConcurrentHashMap \u4fdd\u8bc1\u7684\u662f\u5355\u6b21\u64cd\u4f5c\u7ebf\u7a0b\u5b89\u5168\uff0c\u7ec4\u5408\u66f4\u65b0\u5fc5\u987b\u81ea\u5df1\u7528 replace\/putIfAbsent \u81ea\u65cb\uff0c\u6216\u76f4\u63a5\u4e0a AtomicLongMap\u3002<\/strong><\/p>\n<\/blockquote>\n<\/section>\n","protected":false},"excerpt":{"rendered":"
CAS\uff08Compare and Swap\uff09\u548c ConcurrentHashMap \u7ecf\u5e38\u7ed1\u5728\u4e00\u8d77\u95ee\uff1a\u4e00\u4e2a\u662f\u786c\u4ef6\u7ea7 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[19],"tags":[178,96,177],"_links":{"self":[{"href":"https:\/\/ai.zhousir.top\/index.php?rest_route=\/wp\/v2\/posts\/2086"}],"collection":[{"href":"https:\/\/ai.zhousir.top\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/ai.zhousir.top\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/ai.zhousir.top\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/ai.zhousir.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2086"}],"version-history":[{"count":3,"href":"https:\/\/ai.zhousir.top\/index.php?rest_route=\/wp\/v2\/posts\/2086\/revisions"}],"predecessor-version":[{"id":2107,"href":"https:\/\/ai.zhousir.top\/index.php?rest_route=\/wp\/v2\/posts\/2086\/revisions\/2107"}],"wp:attachment":[{"href":"https:\/\/ai.zhousir.top\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2086"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/ai.zhousir.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2086"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/ai.zhousir.top\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2086"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}