-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
1151 lines (846 loc) · 50.6 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<<<<<<< HEAD
<!DOCTYPE html>
<html lang="en-us">
<head>
<meta charset="UTF-8">
<title>Aries-ckt.GitHub.io by Aries-ckt</title>
<meta name="viewport" content="width=device-width, initial-scale=1">
<link rel="stylesheet" type="text/css" href="stylesheets/normalize.css" media="screen">
<link href='https://fonts.googleapis.com/css?family=Open+Sans:400,700' rel='stylesheet' type='text/css'>
<link rel="stylesheet" type="text/css" href="stylesheets/stylesheet.css" media="screen">
<link rel="stylesheet" type="text/css" href="stylesheets/github-light.css" media="screen">
</head>
<body>
<section class="page-header">
<h1 class="project-name">Aries-ckt.GitHub.io</h1>
<h2 class="project-tagline">Aries-ckt的博客</h2>
</section>
<section class="main-content">
<h1>
<a id="aries-cktgithubio" class="anchor" href="#aries-cktgithubio" aria-hidden="true"><span class="octicon octicon-link"></span></a>Aries-ckt.github.io</h1>
<p>Aries-ckt的博客</p>
<footer class="site-footer">
<span class="site-footer-credits">This page was generated by <a href="https://pages.github.com">GitHub Pages</a> using the <a href="https://github.com/jasonlong/cayman-theme">Cayman theme</a> by <a href="https://twitter.com/jasonlong">Jason Long</a>.</span>
</footer>
</section>
</body>
=======
<!DOCTYPE html>
<!--[if IEMobile 7 ]><html class="no-js iem7"><![endif]-->
<!--[if lt IE 9]><html class="no-js lte-ie8"><![endif]-->
<!--[if (gt IE 8)|(gt IEMobile 7)|!(IEMobile)|!(IE)]><!--><html class="no-js" lang="en"><!--<![endif]-->
<head>
<meta charset="utf-8">
<title>Aries-ckt Blog</title>
<meta name="author" content="Aries-ckt">
<meta name="description" content="并发容器（CopyOnWrite系列，ConcurrentHashMap） copyOnWriteArrayList get()没有加锁 1
2
3
public E get(int index) { return get(getArray(), index);
} add()，加锁 1
2
3 …">
<!-- http://t.co/dKP3o1e -->
<meta name="HandheldFriendly" content="True">
<meta name="MobileOptimized" content="320">
<meta name="viewport" content="width=device-width, initial-scale=1">
<link rel="canonical" href="http://aries-ckt.github.io/">
<link href="/favicon.png" rel="icon">
<link href="/stylesheets/screen.css" media="screen, projection" rel="stylesheet" type="text/css">
<link href="/atom.xml" rel="alternate" title="Aries-ckt Blog" type="application/atom+xml">
<script src="/javascripts/modernizr-2.0.js"></script>
<script src="//ajax.useso.com/ajax/libs/jquery/1.9.1/jquery.min.js"></script>
<script>!window.jQuery && document.write(unescape('%3Cscript src="/javascripts/libs/jquery.min.js"%3E%3C/script%3E'))</script>
<script src="/javascripts/octopress.js" type="text/javascript"></script>
<!--Fonts from Google"s Web font directory at http://google.com/webfonts -->
<link href="//fonts.useso.com/css?family=PT+Serif:regular,italic,bold,bolditalic" rel="stylesheet" type="text/css">
<link href="//fonts.useso.com/css?family=PT+Sans:regular,italic,bold,bolditalic" rel="stylesheet" type="text/css">
</head>
<body >
<header role="banner"><hgroup>
<h1><a href="/">Aries-ckt Blog</a></h1>
<h2>A blogging framework for Aries-ckt.</h2>
</hgroup>
</header>
<nav role="navigation"><ul class="subscription" data-subscription="rss">
<li><a href="/atom.xml" rel="subscribe-rss" title="subscribe via RSS">RSS</a></li>
</ul>
<form action="https://www.google.com/search" method="get">
<fieldset role="search">
<input type="hidden" name="sitesearch" value="aries-ckt.github.io">
<input class="search" type="text" name="q" results="0" placeholder="Search"/>
</fieldset>
</form>
<ul class="main-navigation">
<li><a href="/">Blog</a></li>
<li><a href="/blog/archives">Archives</a></li>
</ul>
</nav>
<div id="main">
<div id="content">
<div class="blog-index">
<article>
<header>
<h1 class="entry-title"><a href="/blog/2016/08/27/javabing-fa-rong-qi/">Java并发容器</a></h1>
<p class="meta">
<time class='entry-date' datetime='2016-08-27T14:47:46+08:00'><span class='date'><span class='date-month'>Aug</span> <span class='date-day'>27</span><span class='date-suffix'>th</span>, <span class='date-year'>2016</span></span> <span class='time'>2:47 pm</span></time>
</p>
</header>
<div class="entry-content"><h3>并发容器（CopyOnWrite系列，ConcurrentHashMap）</h3>
<h4>copyOnWriteArrayList</h4>
<p>get()没有加锁</p>
<figure class='code'><div class="highlight"><table><tr><td class="gutter"><pre class="line-numbers"><span class='line-number'>1</span>
<span class='line-number'>2</span>
<span class='line-number'>3</span>
</pre></td><td class='code'><pre><code class=''><span class='line'>public E get(int index) {
</span><span class='line'> return get(getArray(), index);
</span><span class='line'>}
</span></code></pre></td></tr></table></div></figure>
<p>add()，加锁</p>
<figure class='code'><div class="highlight"><table><tr><td class="gutter"><pre class="line-numbers"><span class='line-number'>1</span>
<span class='line-number'>2</span>
<span class='line-number'>3</span>
<span class='line-number'>4</span>
<span class='line-number'>5</span>
<span class='line-number'>6</span>
<span class='line-number'>7</span>
<span class='line-number'>8</span>
<span class='line-number'>9</span>
<span class='line-number'>10</span>
<span class='line-number'>11</span>
<span class='line-number'>12</span>
<span class='line-number'>13</span>
<span class='line-number'>14</span>
</pre></td><td class='code'><pre><code class=''><span class='line'>public boolean add(E e){
</span><span class='line'> final ReentrantLock lock = this.lock;
</span><span class='line'> lock.lock();
</span><span class='line'> try{
</span><span class='line'> Object[] elements=getArray();
</span><span class='line'> int len=elements.length;
</span><span class='line'> Object[] newElements=Arrays.copyOf(elements,len+1);
</span><span class='line'> newElements[len]=e;
</span><span class='line'> setArray(newElements);
</span><span class='line'> return true;
</span><span class='line'> } finally{
</span><span class='line'> lock.unlock();
</span><span class='line'> }
</span><span class='line'>}</span></code></pre></td></tr></table></div></figure>
<h3>ConcurrentHashMap</h3>
<p>ConcurrentHashMap数据结构：（是一个Segment数组）</p>
<figure class='code'><div class="highlight"><table><tr><td class="gutter"><pre class="line-numbers"><span class='line-number'>1</span>
</pre></td><td class='code'><pre><code class=''><span class='line'>final Segment<K,V>[] segments;</span></code></pre></td></tr></table></div></figure>
<p>Segment的数据结构：（是一个HashEntry的数组）</p>
<figure class='code'><div class="highlight"><table><tr><td class="gutter"><pre class="line-numbers"><span class='line-number'>1</span>
<span class='line-number'>2</span>
<span class='line-number'>3</span>
<span class='line-number'>4</span>
<span class='line-number'>5</span>
</pre></td><td class='code'><pre><code class=''><span class='line'>static final class Segment<K,V> extends ReentrantLock implements Serializable {
</span><span class='line'> ...
</span><span class='line'> transient volatile HashEntry<K,V>[] table; //发现Segment实际上是HashEntry数组
</span><span class='line'> ...
</span><span class='line'>}</span></code></pre></td></tr></table></div></figure>
<p>HashEntry的数据结构：</p>
<figure class='code'><div class="highlight"><table><tr><td class="gutter"><pre class="line-numbers"><span class='line-number'>1</span>
<span class='line-number'>2</span>
<span class='line-number'>3</span>
<span class='line-number'>4</span>
<span class='line-number'>5</span>
<span class='line-number'>6</span>
<span class='line-number'>7</span>
</pre></td><td class='code'><pre><code class=''><span class='line'>static final class HashEntry<K,V> {
</span><span class='line'> final K key;
</span><span class='line'> final int hash;
</span><span class='line'> volatile V value;
</span><span class='line'> final HashEntry<K,V> next;
</span><span class='line'> ...
</span><span class='line'>}</span></code></pre></td></tr></table></div></figure>
<p>所涉及的方法：
不用加锁的：get，containsKey等
段（Segment）内加锁的:put，putIfAbsent，remove，replace等
整个数据结构加锁的：size，containsValue等</p>
<p>构造方法：</p>
<figure class='code'><div class="highlight"><table><tr><td class="gutter"><pre class="line-numbers"><span class='line-number'>1</span>
<span class='line-number'>2</span>
<span class='line-number'>3</span>
<span class='line-number'>4</span>
<span class='line-number'>5</span>
<span class='line-number'>6</span>
<span class='line-number'>7</span>
<span class='line-number'>8</span>
<span class='line-number'>9</span>
<span class='line-number'>10</span>
<span class='line-number'>11</span>
<span class='line-number'>12</span>
<span class='line-number'>13</span>
<span class='line-number'>14</span>
<span class='line-number'>15</span>
<span class='line-number'>16</span>
<span class='line-number'>17</span>
<span class='line-number'>18</span>
<span class='line-number'>19</span>
<span class='line-number'>20</span>
<span class='line-number'>21</span>
<span class='line-number'>22</span>
<span class='line-number'>23</span>
<span class='line-number'>24</span>
<span class='line-number'>25</span>
<span class='line-number'>26</span>
<span class='line-number'>27</span>
<span class='line-number'>28</span>
<span class='line-number'>29</span>
<span class='line-number'>30</span>
</pre></td><td class='code'><pre><code class=''><span class='line'>public ConcurrentHashMap(int initialCapacity,float loadFactor, int concurrencyLevel) {
</span><span class='line'> if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
</span><span class='line'> throw new IllegalArgumentException(); //参数合法性校验
</span><span class='line'> if (concurrencyLevel > MAX_SEGMENTS)
</span><span class='line'> concurrencyLevel = MAX_SEGMENTS;
</span><span class='line'> //比如我输入的concurrencyLevel=12，那么sshift = 4，ssize =16，所以sshift是意思就是1左移了几次比concurrencyLevel大，ssize就是那个大于等于concurrencyLevel的最小2的幂次方的数
</span><span class='line'> int sshift = 0;
</span><span class='line'> int ssize = 1;
</span><span class='line'> while (ssize < concurrencyLevel) {
</span><span class='line'> ++sshift;
</span><span class='line'> ssize <<= 1; //ssize = ssize << 1 , ssize = ssize * 2
</span><span class='line'> }
</span><span class='line'> segmentShift = 32 - sshift;
</span><span class='line'> segmentMask = ssize - 1; //segmentMask的二进制是一个全是1的数
</span><span class='line'> this.segments = Segment.newArray(ssize); //segment个数是ssize，也就是上图黄色方块数，默认16个
</span><span class='line'> if (initialCapacity > MAXIMUM_CAPACITY)
</span><span class='line'> initialCapacity = MAXIMUM_CAPACITY;
</span><span class='line'> int c = initialCapacity / ssize;
</span><span class='line'> if (c * ssize < initialCapacity)
</span><span class='line'> ++c;
</span><span class='line'> int cap = 1;
</span><span class='line'> while (cap < c)
</span><span class='line'> cap <<= 1;
</span><span class='line'> for (int i = 0; i < this.segments.length; ++i)
</span><span class='line'> this.segments[i] = new Segment<K,V>(cap, loadFactor);//上图浅绿色块的个数是cap，是一个2的幂次方的数，默认是1，也就是每个segment下都构造了cap大小的table数组
</span><span class='line'>}
</span><span class='line'>Segment(int initialCapacity, float lf) {
</span><span class='line'> loadFactor = lf;
</span><span class='line'> setTable(HashEntry.<K,V>newArray(initialCapacity));//构造了一个initialCapacity大小的table
</span><span class='line'>}</span></code></pre></td></tr></table></div></figure>
<p>put方法：</p>
<figure class='code'><div class="highlight"><table><tr><td class="gutter"><pre class="line-numbers"><span class='line-number'>1</span>
<span class='line-number'>2</span>
<span class='line-number'>3</span>
<span class='line-number'>4</span>
<span class='line-number'>5</span>
<span class='line-number'>6</span>
<span class='line-number'>7</span>
<span class='line-number'>8</span>
<span class='line-number'>9</span>
<span class='line-number'>10</span>
<span class='line-number'>11</span>
<span class='line-number'>12</span>
<span class='line-number'>13</span>
<span class='line-number'>14</span>
<span class='line-number'>15</span>
<span class='line-number'>16</span>
<span class='line-number'>17</span>
<span class='line-number'>18</span>
<span class='line-number'>19</span>
<span class='line-number'>20</span>
<span class='line-number'>21</span>
<span class='line-number'>22</span>
<span class='line-number'>23</span>
<span class='line-number'>24</span>
<span class='line-number'>25</span>
<span class='line-number'>26</span>
<span class='line-number'>27</span>
<span class='line-number'>28</span>
<span class='line-number'>29</span>
<span class='line-number'>30</span>
<span class='line-number'>31</span>
<span class='line-number'>32</span>
<span class='line-number'>33</span>
<span class='line-number'>34</span>
<span class='line-number'>35</span>
<span class='line-number'>36</span>
<span class='line-number'>37</span>
<span class='line-number'>38</span>
<span class='line-number'>39</span>
<span class='line-number'>40</span>
<span class='line-number'>41</span>
</pre></td><td class='code'><pre><code class=''><span class='line'>public V put(K key, V value) {
</span><span class='line'> if (value == null)
</span><span class='line'> throw new NullPointerException(); //明确指定value不能为null
</span><span class='line'> int hash = hash(key.hashCode());
</span><span class='line'> return segmentFor(hash).put(key, hash, value, false); //segmentFor如下，定位segment下标，然后再put
</span><span class='line'>}
</span><span class='line'>
</span><span class='line'>final Segment<K,V> segmentFor(int hash) { //寻找segment的下标
</span><span class='line'> return segments[(hash >>> segmentShift) & segmentMask]; //前面说了segmentMask是一个2进制全是1的数，那么&segmentMask就保证了下标小于等于segmentMask，与HashMap的寻下标相似。
</span><span class='line'>}
</span><span class='line'>
</span><span class='line'>//真正的put操作
</span><span class='line'>V put(K key, int hash, V value, boolean onlyIfAbsent) {
</span><span class='line'> lock(); //先加锁，可以看到，put操作是在segment里面加锁的，也就是每个segment都可以加一把锁
</span><span class='line'> try {
</span><span class='line'> int c = count;
</span><span class='line'> if (c++ > threshold) // ensure capacity
</span><span class='line'> rehash(); //判断容量，如果不够了就扩容
</span><span class='line'> HashEntry<K,V>[] tab = table; //将table赋给一个局部变量tab，这是因为table是volatile变量，读写volatile变量的开销很大，编译器也不能对volatile变量的读写做任何优化，直接多次访问非volatile实例变量没有多大影响，编译器会做相应优化。
</span><span class='line'> int index = hash & (tab.length - 1); //寻找table的下标
</span><span class='line'> HashEntry<K,V> first = tab[index];
</span><span class='line'> HashEntry<K,V> e = first;
</span><span class='line'> while (e != null && (e.hash != hash || !key.equals(e.key)))
</span><span class='line'> e = e.next; //遍历单链表，找到key相同的为止，如果没找到，e指向链表尾
</span><span class='line'>
</span><span class='line'> V oldValue;
</span><span class='line'> if (e != null) { //如果有相同的key，那么直接替换
</span><span class='line'> oldValue = e.value;
</span><span class='line'> if (!onlyIfAbsent)
</span><span class='line'> e.value = value;
</span><span class='line'> }
</span><span class='line'> else { //否则在链表表头插入新的结点
</span><span class='line'> oldValue = null;
</span><span class='line'> ++modCount;
</span><span class='line'> tab[index] = new HashEntry<K,V>(key, hash, first, value);
</span><span class='line'> count = c; // write-volatile
</span><span class='line'> }
</span><span class='line'> return oldValue;
</span><span class='line'> } finally {
</span><span class='line'> unlock();
</span><span class='line'> }</span></code></pre></td></tr></table></div></figure>
<p>该方法也是在持有段锁的情况下执行的，首先判断是否需要rehash，需要就先rehash，扩容都是针对单个段的，也就是单个段的数据数量大于设定的量的时候会触发扩容。接着是找是否存在同样一个key的结点，如果存在就直接替换这个结点的值。否则创建一个新的结点并添加到hash链的头部，这时一定要修改modCount和count的值，同样修改count的值一定要放在最后一步。put方法调用了rehash方法，reash方法实现得也很精巧，主要利用了table的大小为2<sup>n</sup>，和HashMap的扩容基本一样，这里就不介绍了。</p>
<p>还有一个叫putIfAbsent(K key, V value)的函数，这个函数的实现和put几乎一模一样，作用是，如果map中不存在这个key，那么插入这个数据，如果存在这个key，那么不覆盖原来的value，也就是不插入了。</p>
<p>get方法</p>
<figure class='code'><div class="highlight"><table><tr><td class="gutter"><pre class="line-numbers"><span class='line-number'>1</span>
<span class='line-number'>2</span>
<span class='line-number'>3</span>
<span class='line-number'>4</span>
<span class='line-number'>5</span>
<span class='line-number'>6</span>
<span class='line-number'>7</span>
<span class='line-number'>8</span>
<span class='line-number'>9</span>
<span class='line-number'>10</span>
<span class='line-number'>11</span>
<span class='line-number'>12</span>
<span class='line-number'>13</span>
<span class='line-number'>14</span>
<span class='line-number'>15</span>
<span class='line-number'>16</span>
<span class='line-number'>17</span>
<span class='line-number'>18</span>
<span class='line-number'>19</span>
<span class='line-number'>20</span>
<span class='line-number'>21</span>
<span class='line-number'>22</span>
<span class='line-number'>23</span>
<span class='line-number'>24</span>
<span class='line-number'>25</span>
<span class='line-number'>26</span>
<span class='line-number'>27</span>
<span class='line-number'>28</span>
<span class='line-number'>29</span>
</pre></td><td class='code'><pre><code class=''><span class='line'>public V get(Object key) {
</span><span class='line'> int hash = hash(key.hashCode()); //双hash，和HashMap一样，也是为了更好的离散化
</span><span class='line'> return segmentFor(hash).get(key, hash); //先寻找segment的下标，然后再get
</span><span class='line'>}
</span><span class='line'>
</span><span class='line'>final Segment<K,V> segmentFor(int hash) { //寻找segment的下标
</span><span class='line'> return segments[(hash >>> segmentShift) & segmentMask]; //前面说了segmentMask是一个2进制全是1的数，那么&segmentMask就保证了下标小于等于segmentMask，与HashMap的寻下标相似。
</span><span class='line'>}
</span><span class='line'>
</span><span class='line'>V get(Object key, int hash) {// count是一个volatile变量，count非常巧妙，每次put和remove之后的最后一步都要更新count，就是为了get的时候不让编译器对代码进行重排序，来保证
</span><span class='line'> if (count != 0) {
</span><span class='line'> HashEntry<K,V> e = getFirst(hash); //寻找table的下标，也就是链表的表头
</span><span class='line'> while (e != null) {
</span><span class='line'> if (e.hash == hash && key.equals(e.key)) {
</span><span class='line'> V v = e.value;
</span><span class='line'> if (v != null)
</span><span class='line'> return v;
</span><span class='line'> return readValueUnderLock(e); // recheck 加锁读，这个加锁读不用重新计算位置，而是直接拿e的值
</span><span class='line'> }
</span><span class='line'> e = e.next;
</span><span class='line'> }
</span><span class='line'> }
</span><span class='line'> return null;
</span><span class='line'>}
</span><span class='line'>
</span><span class='line'>HashEntry<K,V> getFirst(int hash) {
</span><span class='line'> HashEntry<K,V>[] tab = table;
</span><span class='line'> return tab[hash & (tab.length - 1)];
</span><span class='line'>}</span></code></pre></td></tr></table></div></figure>
<p>size方法：</p>
<figure class='code'><div class="highlight"><table><tr><td class="gutter"><pre class="line-numbers"><span class='line-number'>1</span>
<span class='line-number'>2</span>
<span class='line-number'>3</span>
<span class='line-number'>4</span>
<span class='line-number'>5</span>
<span class='line-number'>6</span>
<span class='line-number'>7</span>
<span class='line-number'>8</span>
<span class='line-number'>9</span>
<span class='line-number'>10</span>
<span class='line-number'>11</span>
<span class='line-number'>12</span>
<span class='line-number'>13</span>
<span class='line-number'>14</span>
<span class='line-number'>15</span>
<span class='line-number'>16</span>
<span class='line-number'>17</span>
<span class='line-number'>18</span>
<span class='line-number'>19</span>
<span class='line-number'>20</span>
<span class='line-number'>21</span>
<span class='line-number'>22</span>
<span class='line-number'>23</span>
<span class='line-number'>24</span>
<span class='line-number'>25</span>
<span class='line-number'>26</span>
<span class='line-number'>27</span>
<span class='line-number'>28</span>
<span class='line-number'>29</span>
<span class='line-number'>30</span>
<span class='line-number'>31</span>
<span class='line-number'>32</span>
<span class='line-number'>33</span>
<span class='line-number'>34</span>
<span class='line-number'>35</span>
<span class='line-number'>36</span>
<span class='line-number'>37</span>
<span class='line-number'>38</span>
<span class='line-number'>39</span>
<span class='line-number'>40</span>
<span class='line-number'>41</span>
</pre></td><td class='code'><pre><code class=''><span class='line'>public int size() {
</span><span class='line'> final Segment<K,V>[] segments = this.segments;
</span><span class='line'> long sum = 0;
</span><span class='line'> long check = 0;
</span><span class='line'> int[] mc = new int[segments.length];
</span><span class='line'> // Try a few times to get accurate count. On failure due to
</span><span class='line'> // continuous async changes in table, resort to locking.
</span><span class='line'> for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
</span><span class='line'> check = 0;
</span><span class='line'> sum = 0;
</span><span class='line'> int mcsum = 0;
</span><span class='line'> for (int i = 0; i < segments.length; ++i) {
</span><span class='line'> sum += segments[i].count; //循环相加每个段内数据的个数
</span><span class='line'> mcsum += mc[i] = segments[i].modCount; //循环相加每个段内的modCount
</span><span class='line'> }
</span><span class='line'> if (mcsum != 0) { //如果是0，代表根本没有过数据更改，也就是size是0
</span><span class='line'> for (int i = 0; i < segments.length; ++i) {
</span><span class='line'> check += segments[i].count; //再次循环相加每个段内数据的个数，这里为什么会再算一次呢，后面会说
</span><span class='line'> if (mc[i] != segments[i].modCount) {
</span><span class='line'> check = -1; // force retry //如果modCount和之前统计的不一致了，check直接赋值-1，重新再来
</span><span class='line'> break;
</span><span class='line'> }
</span><span class='line'> }
</span><span class='line'> }
</span><span class='line'> if (check == sum)
</span><span class='line'> break;
</span><span class='line'> }
</span><span class='line'> if (check != sum) { // Resort to locking all segments
</span><span class='line'> sum = 0;
</span><span class='line'> for (int i = 0; i < segments.length; ++i) //循环获取所有segment的锁
</span><span class='line'> segments[i].lock();
</span><span class='line'> for (int i = 0; i < segments.length; ++i) //在持有所有段的锁的时候进行count的相加
</span><span class='line'> sum += segments[i].count;
</span><span class='line'> for (int i = 0; i < segments.length; ++i) //循环释放所有段的锁
</span><span class='line'> segments[i].unlock();
</span><span class='line'> }
</span><span class='line'> if (sum > Integer.MAX_VALUE) //return
</span><span class='line'> return Integer.MAX_VALUE;
</span><span class='line'> else
</span><span class='line'> return (int)sum;
</span><span class='line'>}</span></code></pre></td></tr></table></div></figure>
<p> 如果我们要统计整个ConcurrentHashMap里元素的大小，就必须统计所有Segment里元素的大小后求和。Segment里的全局变量count是一个volatile变量，那么在多线程场景下，我们是不是直接把所有Segment的count相加就可以得到整个ConcurrentHashMap大小了呢？不是的，虽然相加时可以获取每个Segment的count的最新值，但是拿到之后可能累加前使用的count发生了变化，那么统计结果就不准了。所以最安全的做法，是在统计size的时候把所有Segment的put，remove和clean方法全部锁住，但是这种做法显然非常低效，因为在累加count操作过程中，之前累加过的count发生变化的几率非常小，所以ConcurrentHashMap的做法是先尝试2次通过不锁住Segment的方式来统计各个Segment大小，如果统计的过程中，容器的count发生了变化，则再采用加锁的方式来统计所有Segment的大小。那么ConcurrentHashMap是如何判断在统计的时候容器是否发生了变化呢？使用modCount变量，在put , remove和clear方法里操作元素前都会将变量modCount进行加1，那么在统计size前后比较modCount是否发生变化，从而得知容器的大小是否发生变化。size()的实现还有一点需要注意，必须要先segments[i].count，才能segments[i].modCount，这是因为segment[i].count是对volatile变量的访问，接下来segments[i].modCount才能得到几乎最新的值，这里和get方法的方式是一样的，也是一个volatile写 happens-before volatile读的问题。</p>
<p>上面18行代码，抛出了一个问题，就是为什么会再算一遍，上面说只需要比较modCount不变不就可以了么？但是仔细分析，就会发现，在13行14行代码那里，计算完count之后，计算modCount之前有可能count的值又变了，那么18行的代码主要是解决这个问题。</p>
</div>
</article>
<article>
<header>
<h1 class="entry-title"><a href="/blog/2015/09/20/innerclass/">InnerClass</a></h1>
<p class="meta">
<time class='entry-date' datetime='2015-09-20T19:24:08+08:00'><span class='date'><span class='date-month'>Sep</span> <span class='date-day'>20</span><span class='date-suffix'>th</span>, <span class='date-year'>2015</span></span> <span class='time'>7:24 pm</span></time>
</p>
</header>
<div class="entry-content"><h2>内部类</h2>
<p>内部类是定义在一个类内部的类，特点：
1.内部类可以直接访问外部内中的成员变量。内部类要访问局部变量必须将局部变量用final修饰。
2.内部类有两种定义方式，一种定义在方法体内，另外一种定义在方法体外。区别在于在方法体外了一定以3内部类的访问类型，可以使public,protected以及默认的。而不能在方法体内定义内部类的访问类型。
3.内部类不能定义静态成员。
4.静态内部类，在方法外部定义的内部类前面可以加上static关键字，从而成为Staic Nested Class,不再具备内部类的特征了。
简单写一个匿名内部类例子(线程)</p>
<pre class="brush:java;gutter:true;">
public class Outer{
pubic void start(){
new Tread(
new Runnable(){
public void run(){}
}).start();
}
}
</pre>
</div>
</article>
<article>
<header>
<h1 class="entry-title"><a href="/blog/2015/09/06/spring-security/">Spring-security</a></h1>
<p class="meta">
<time class='entry-date' datetime='2015-09-06T21:01:45+08:00'><span class='date'><span class='date-month'>Sep</span> <span class='date-day'>6</span><span class='date-suffix'>th</span>, <span class='date-year'>2015</span></span> <span class='time'>9:01 pm</span></time>
</p>
</header>
<div class="entry-content"><h2>spring-security授权以及验证方法总结</h2>
<p>其授权验证方法过程：
1、当Web服务器启动时，通过Web.xml中对于Spring Security的配置，加载过滤器链，那么在加载MyFilterSecurityInterceptor类时，会注入 MyInvocationSecurityMetadataSourceService、MyUserDetailsService、 MyAccessDecisionManager类。</p>
<p> 2、该MyInvocationSecurityMetadataSourceService类在执行时会提取数据库中所有的用户权限，形成权限列表；
并循环该权限列表，通过每个权限再从数据库中提取出该权限所对应的资源列表，并将资源（URL）作为key，权限列表作为value，形成Map结构的数据。</p>
<p> 3、当用户登录时，AuthenticationManager进行响应，通过用户输入的用户名和密码，然后再根据用户定义的密码算法和盐值等进行计算并和数据库比对，
当正确时通过验证。此时MyUserDetailsService进行响应，根据用户名从数据库中提取该用户的权限列表，组合成UserDetails供Spring Security使用。</p>
<p> 4、当用户点击某个功能时，触发MyAccessDecisionManager类，该类通过decide方法对用户的资源访问进行拦截。
用户点击某个功能时，实际上是请求某个URL或Action， 无论.jsp也好，.action或.do也好，在请求时无一例外的表现为URL。
还记得第2步时那个Map结构的数据吗？ 若用户点击了"login.action"这个URL之后，那么这个URL就跟那个Map结构的数据中的key对比，若两者相同，
则根据该url提取出Map结构的数据中的value来，这说明：若要请求这个URL，必须具有跟这个URL相对应的权限值。这个权限有可能是一个单独的权限，
也有可能是一个权限列表，也就是说，一个URL有可能被多种权限访问。</p>
<p> 那好，我们在MyAccessDecisionManager类的decide这个方法里，将通过URL取得的权限列表进行循环，然后跟第 3步中登录的用户所具有的权限进行比对，若相同，则表明该用户具有访问该资源的权利。 不大明白吧？ 简单地说， 在数据库中我们定义了访问“LOGIN”这个URL必须是具有ROLE_ADMIN权限的人来访问，那么，登录用户恰恰具有该ROLE_ADMIN权限， 两者的比对过程中，就能够返回TRUE，可以允许该用户进行访问。就这么简单！</p>
<p>不过在第2步的时候，一定要注意，MyInvocationSecurityMetadataSoruceService类的loadResourceDefine()方法中，形成以URL为key，权限列表为value的Map时，
要注意key和Value的对应性，避免Value的不正确对应形成重复，这样会导致没有权限的人也能访问到不该访问到的资源。
还有getAttributes()方法，要有 url.indexOf(“?”)这样的判断，要通过判断对URL特别是Action问号之前的部分进行匹配，防止用户请求的带参数的URL与你数据库中定义的URL不匹配，造成访问拒绝！</p>
</div>
</article>
<article>
<header>
<h1 class="entry-title"><a href="/blog/2015/09/05/bashji-chu-cao-zuo/">Bash基础操作</a></h1>
<p class="meta">
<time class='entry-date' datetime='2015-09-05T15:35:47+08:00'><span class='date'><span class='date-month'>Sep</span> <span class='date-day'>5</span><span class='date-suffix'>th</span>, <span class='date-year'>2015</span></span> <span class='time'>3:35 pm</span></time>
</p>
</header>
<div class="entry-content"><h2>bash基础操作</h2>
<p>bash应该是目前Linux上最流行的shell脚本解释程序了（还有个shell叫dash），</p>
<h3>变量</h3>
<p>1、bash的变量名是区分大小写的，并且变量名首字符不能是数字。看的各种代码也不少了，说实话，我还真没见到谁的代码用数字开头的变量名，我认为即使语言允许，这样做的人也很少，除非你真的很特别。</p>
<p>2、变量定义与赋值
aaa=123
这里需要注意定义变量时等号前后都不能有空格，必须紧靠着写。虽然等号后面有空格的情况，语法可能不会出错，但结果绝对是错误的。</p>
<p>3、变量拼接
bbb=${aaa}123
很多时候，我们可能需要用一些变量、常量字符串等来拼接出一个新的变量，这时需要注意用来拼接的变量可能需要加上{}，否则可能会出现变量识别错误从而找不到变量的情况。这种情况，我倾向于所有变量一股脑的全加上{}。</p>
<p>4、local和export
变量定义时还有两个常用的关键字——local和export。export在下文再说，定义局部变量的local，我却基本不用，等我使用的时候再来补上总结。</p>
<h3>条件判断</h3>
<p>if条件表达中长涉及到的比较有字符串、整数和文件属性比较等。
if语句格式有：
if [ expr ] ; then
do something
fi</p>
<p>if [ expr ] ; then
do something
else
do something
fi</p>
<p>if [ expr ] ; then
do something
elif [ expr ] ; then
do something
else
so something
fi</p>
<p>if语句和其他语言（c,java）相比，是行不同但神似。then关键可以另起一行，那样条件表达式后的分号就可以省略了。这里最需要注意的是 “ [ ” 和 “ ] "前后至少需要一个空格来分割。</p>
<p>1、整数比较
整数大小比较涉及的操作符有—— -lt、-le、-eq、-gt、-ge和 -ne。
例子：
a=1
b=2</p>
<p>if [ $a -lt $b ] ; then
echo “a < b”
else
echo “a >= b”
fi</p>
<p>if [ $a -ne 3 ] ; then
echo “a != 3”
else
echo “a == 3”
fi</p>
<p>if [ 1 -gt 3 ] ; then
echo “1 > 3”
else
echo “1 <= 3”
fi</p>
<p>使用整数大小比较的6个操作符时，涉及到的两个操作数将会作为数值来处理，而不是字符串，即使你使用双引号将比较对象给引起来，也是如此。</p>
<p>2、字符串比较
字符串比较可能用到的操作符有—— =、！=、>、<、-n和-z。
例子：
s1=aaa
s2=bbb</p>
<p>if [ $s1 < $s2 ] ; then
echo “$s1 < $s2”
else
echo “$s1 >= $s2”
fi</p>
<p>if [[ $s1 < $s2 ]] ; then
echo “$s1 < $s2”
else
echo “$s1 >= $s2”
fi</p>
<p>if [ $s1 = $s2 ] ; then
echo “$s1 == $s2”
else
echo “$s1 != $s2”
fi</p>
<p>if [ -n $s1 ] ; then
echo $s1
fi
用于字符串大小比较的>和<两个操作符比较特别，在[ ]中书写时需要转义，否则可以使用[[ ]]来替代[ ]。不转义，>和<会被解释为IO重定向操作。其次，if语句体不能为空，必须至少做一件事情。</p>
<p>操作符-n 用于判断字符串不为空，即长度不为0。-z判断字符串为空，即长度为0。</p>
<p>3、文件属性判断
文件属性判断涉及到的操作符比较多，如下：
-e、-a：文件存在
-d：是目录
-f：是文件
-r：可读
-w：可写
-x：可执行
f1 -nt f2：f1比f2新
f1 -ot f2：f1比f2老</p>
<h3>for循环</h3>
<p>常用的for循环有两种主要形式
形式一
for e in [list]
do
do something
done
这种格式的for常用来遍历一个list集合中的所有元素，并加以处理。比如：
1、遍历一个目录中的所有文件
for file in <code>ls dir</code>
do
echo $file
done</p>
<p>2、遍历一个给定的集合
list=“a b c d e f g”
for e in $list
do
echo $e
done</p>
<p>for in格式在遍历集合时，其实是根据空白字符来分隔字符串，取得每个元素的，上例中的<code>ls dir</code>和$list得到的都是一个带空白字符的字符串。</p>
<p>形式二
for ((i = 0; i < n; i++))
do
do something
done
这一种for的形式和C语言基本一致，只是需要双括号罢了，它更擅长做确定次数的循环计算。比如：</p>
<p>for ((i = 0; i < 10; i++))
do
echo $i
done</p>
<p>for (( ; ; ))
do
echo “aaaa”
done
没有计数器的for循环就是一个死循环的实现，这和C语言的写法也是一致的，真有亲切感。</p>
<h3>case语句</h3>
<p>case语句相当于绝大多数语言里的switch语句。这玩意除了具备if-elif的功能外，还支持通配符，这个相当有用。我们直接看例子。
例子：
url=www.tmall.com</p>
<p>case $url in
www.taobao.com) echo 1;;
<em>.taobao.com) echo 2;;
</em>.tmall.com) echo 3;;
www.tmall.com) echo 4;;
*) echo 5;;
esac</p>
<p>上例中条件分支不光有常量字符串，还有含通配符的字符串，这一点用来进行模式匹配非常便利。其次，需要注意case语言在匹配的过程中是从第一个开始逐一匹配，所有上例的输出结果是3,而不是精确匹配的4。我认为这算一个小小的遗憾，要是支持精确匹配优先就更好玩了。</p>
<p>其次，需要注意的是每个条件分支体的结束必须用双分号。</p>
<p>好了，case语言比较简单，但很实用。</p>
<h3>函数</h3>
<p>函数定义
function hello()
{
echo “hello world”
}
函数定义实用关键字function，函数名后面的括号可有可无。</p>
<p>函数调用
无参数的函数调用只需要给出函数名就ok了，上面定义的函数直接用hello调用即可。有参数的函数，只需要将参数依次在函数名后面给出即可，如：func_name arg1 arg2。</p>
<p>函数参数
函数调用的时候可以给函数传递参数，那么函数体中又如何获取这些参数呢？ 函数参数的获取和脚本程序参数的获取一致，都是通过$1、$2等来取得。比如：
function add()
{
n=$1
m=$2
echo $((n + m))
}</p>
<p>调用add 1 2，将输出3。</p>
<p>在函数中，可以通过$#的值来判断函数调用的时候，传递了几个参数。</p>
<p>bash函数里很少使用return这种方式来返回值。不过可以这样调用函数来获取计算结果，比如：</p>
<p>res=<code>add 1 2</code>
变量res的值就是3了。注意上面不是单引号，而是数字1旁边的字符。</p>
<h3>字符串处理</h3>
<p>C语言的人很多事情都是在编写字符串处理程序。玩java的人大多数时候虽然不用自己去编写字符串处理程序，但也基本总是在调用字符串处理方法。linux其实有着非常强大的工具让我们去做字符串处理，不熟悉之前，每个工具貌似长得都非常复杂的样子。这里简单的总结一下自己使用过的字符串相关的东东。</p>
<p>1、求子串
str=abcdefg
echo ${str:2:3} 将得到bcd，表达式中的2代表偏移量，3代表长度。</p>
<p>2、求字符串长度
str=123456
echo ${#str}</p>
<p>3、字符串替换
${变量/pattern/xx} 将变量中的第一个匹配替换为xx。
${变量//pattern/xx} 将变量中的所有匹配替换为xx。</p>
<p>str=aaabbbccc
echo ${str/aaa/xxx}
echo ${str/a/x}</p>
<p>有关字符串的处理，有着很多的工具，比如：你可以使用cut, awk等程序去拆分一个字符串等。</p>
<h3>整数运算</h3>
<p>整数运算一般使用$(( expr ))来进行。比如：
echo $((1 + 2))
a=1
echo $((a + 2))
echo $((a++))
echo $((++a))
b=2
echo $(((a + b) / 2))</p>
<p>可以看到只需要将计算表达式塞到$(())中就可以了，参与计算的变量并不需要$符号。整数运算涉及到的运算符有：++ 、–、+、-、*、/、%、+=、**(幂运算); 还有不常用的：<<、 >>、 ^、 &、 !、 |、 ~，这些在C语言中倒挺常用的，shell用来做这些位运算的需求也太2b了。 除了这些运算还支持逻辑：<、>、<=、>=、==、!=、&&、||。</p>
<p>$(( expr ))表达式只能计算整数，不能用于小数的计算。如果，要做小数的计算，可以使用linux上的命令行计算器bc来完成。
例子：
echo “1.5 + 1” | bc</p>
<h3>代码生成</h3>
<p>程序员应该是”懒惰“的，”懒惰“的程序员可以创造出更多的自动化工具。我喜欢用bash来辅助我完成一些代码的自动生成，当然不是所有的代码都可以自动生成，如果那样也就不需要程序员了。我认为好的程序一定是可扩展的，最好的可扩展程序是”完成程序框架等开发后的功能需求开发阶段不再需要过分的写代码，只需要填代码“，能够填的代码，一定是可以自动生成的，这样的程序开发就将形成一个良性的循环。重构代码，尽量让代码可以用bash脚本来自动生成，这将极大的提高开发效率。</p>
<p>如何自动生成代码，生成什么样的代码，是根据自己的实际情况来完成的，这里没法介绍具体的代码生成，只能介绍bash用来完成代码生成的工具——cat。使用过linux的人都知道cat，这里就不详细说明了，只展示一段简单的bash脚本输出hello world程序。</p>
<h1>!/bin/sh</h1>
<p>cat << END > hello.c</p>
<h1>include <stdio.h></h1>
<p>int main(void)
{
printf(“hello world\n”);
return 0;
}
END</p>
<p>在cat到END之间，你可以像在编辑器里一样编写自己的代码，这里写成什么样子，输出到源文件里就是什么样子，包括缩进等格式。当然，真正有意义的代码生成不会像这里的hello world这么简单，你必须得根据自己的实际情况去”拼凑“出自动化的代码。这里仅仅是展示使用cat来生成一个源码文件而已。要想自动生成真正有意义的，能提高自己开发效率的代码，必须得学习绝大多数的bash编程知识。</p>
<h3>逐行读文件</h3>
<p>当你在做文本处理的时候，可能需要将一个文件的内容一行一行的依次读出，然后加以处理，bash做这个事情是非常的方便的。
例子：
while read line
do
echo $line
done < txt.log
例子展示的是从文件txt.log中逐行的读出来赋值给变量line。如果，你的文件内容是结构化的，比如：每行都是两列，你想单独的处理每一列的内容，那么bash提供了更友好的方式去逐行读文件。
例子：
while read c1 c2
do
echo $c1 : $c2
done
这样read文件，第一列就赋值给了c1，第二列就赋值给了c2。这有点ruby，python，go等优秀语言支持的多变量赋值的味道。</p>
</div>
</article>
<article>
<header>
<h1 class="entry-title"><a href="/blog/2015/08/28/transientguan-jian-zi/">Transient关键字</a></h1>
<p class="meta">
<time class='entry-date' datetime='2015-08-28T21:22:17+08:00'><span class='date'><span class='date-month'>Aug</span> <span class='date-day'>28</span><span class='date-suffix'>th</span>, <span class='date-year'>2015</span></span> <span class='time'>9:22 pm</span></time>
</p>
</header>
<div class="entry-content"><h1>transient关键字作用及使用方法！</h1>
<p>我们都知道一个对象只要实现了Serilizable接口，这个对象就可以被序列化，java的这种序列化模式为开发者提供了很多便利，我们可以不必关系具体序列化的过程，只要这个类实现了Serilizable接口，这个类的所有属性和方法都会自动序列化。</p>
<p>然而在实际开发过程中，我们常常会遇到这样的问题，这个类的有些属性需要序列化，而其他属性不需要被序列化，打个比方，如果一个用户有一些敏感信息（如密码，银行卡号等），为了安全起见，不希望在网络操作（主要涉及到序列化操作，本地序列化缓存也适用）中被传输，这些信息对应的变量就可以加上transient关键字。换句话说，这个字段的生命周期仅存于调用者的内存中而不会写到磁盘里持久化。</p>
<p>总之，java 的transient关键字为我们提供了便利，你只需要实现Serilizable接口，将不需要序列化的属性前添加关键字transient，序列化对象的时候，这个属性就不会序列化到指定的目的地中。</p>
<h1>transient使用小结</h1>
<p>1）一旦变量被transient修饰，变量将不再是对象持久化的一部分，该变量内容在序列化后无法获得访问。</p>
<p>2）transient关键字只能修饰变量，而不能修饰方法和类。注意，本地变量是不能被transient关键字修饰的。变量如果是用户自定义类变量，则该类需要实现Serializable接口。</p>
<p>3）被transient关键字修饰的变量不再能被序列化，一个静态变量不管是否被transient修饰，均不能被序列化。</p>
</div>
</article>
<article>
<header>
<h1 class="entry-title"><a href="/blog/2015/08/15/serializble/">“Java序列化”</a></h1>
<p class="meta">
<time class='entry-date' datetime='2015-08-15T12:31:15+08:00'><span class='date'><span class='date-month'>Aug</span> <span class='date-day'>15</span><span class='date-suffix'>th</span>, <span class='date-year'>2015</span></span> <span class='time'>12:31 pm</span></time>
</p>
</header>