JavaのArrayDequeのソースコードを読んでみた
最近Javaのコアのソースコードをちょくちょく読むのでその感想をまとめてみた。
話すこと
java.utilパッケージ内のArrayDequeのソースコードの主要なところを呼んでみた感想
javaのソースコードを参照する方法
javaのソースコードの探し方は こちら を参考にした。
対象のバージョン
% java -version
openjdk version "11.0.11" 2021-04-20
OpenJDK Runtime Environment AdoptOpenJDK-11.0.11+9 (build 11.0.11+9)
OpenJDK 64-Bit Server VM AdoptOpenJDK-11.0.11+9 (build 11.0.11+9, mixed mode)
ArrayDequeって何?
Javaにおける先頭または後ろから要素を挿入、取り出すことことに特化したデータ構造である。
キューの進化版といったイメージ。
メンバ変数
3つのメンバ変数を持っている。
- Object型の配列のelements
- この配列内に我々が保持したい要素が入る。デフォルトのサイズは16で足りなくなれば増える。
- int型のhead
- elements内のどのインデックスが現在の先頭かを把握するために使われる。
- int型のtail
- elements内のどのインデックスが現在の最後尾かを把握するために使われる。
headとtailの役割
elementsには配列なので線形のデータ構造だが、ここではリングバッファのように使われている。
つまり配列の最後尾と先頭をつなげて円のようにして使っている。
そうすることで早い段階で使われなくなってしまった最初の方のスロットを再利用することができる。
しかしその便利そうなリングバッファにも欠点があり、要素の挿入、削除を繰り返していくと配列内のどこが先頭でどこが最後尾か分からなくなる。
その点を解決するためにhead,tailの二つのメンバ変数を定義し常に追跡しているのだと思う。
次に代表的なメソッドの中を見てみた。
addLast(E e)
- やっていることはキューの一番後ろに要素を入れること
- ソースコードは以下のようになっている
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
final Object[] es = elements;
es[tail] = e;
if (head == (tail = inc(tail, es.length)))
grow(1);
}
やっていることはシンプルで最後尾(tail)に要素を新しく入れている。
そしてheadと新しいtailが同じ値だったらちょうど一周していることになるためgrowメソッドを呼びスロットを増やしている。
head == (tail = inc(tail, es.length))のように変数に代入しつつそのまま他の要素の比較することができるのは知らなかった。
ちなみにincというのがhead,tailを操作しているメソッドで引数に渡された数字を+1または最後尾だったら0にしている。
ソースコードはこちら
static final int inc(int i, int modulus) {
if (++i >= modulus) i = 0;
return i;
}
引数iは現在のインデックスi、配列の長さmodulusが渡される。
iを+1してmodulusに達していたら先頭つまり0に戻す。
++iと書くことによってインクリメントしつつmodulusとの比較を可能にしている。
isEmpty()
public boolean isEmpty() { return head == tail; }
こちらはすごいシンプルである。
一瞬?となったが要素が一個でも入っていればtailはheadと違う値になるはずなので、なるほどなとなった。
peekFirst()
public E peekFirst() { return elementAt(elements, head); }
elementAtに配列とheadを渡しているこちらもシンプルだ。
ちなみにEというのは型パラメータというもので、クラスを初期化する時に型も一緒に渡すことで動的に型を変えることができる。
elementAtも見てみた。
static final <E> E elementAt(Object[] es, int i) {
return (E) es[i];
}
ロジック自体は特筆するところはないがstaticが少し気になった。
メンバ変数のelements[]に対して使われているのでインスタンスメソッドとして実装されるものだと思っていたが、なぜスタティックメソッドなのだろうか。
他の配列にも使われるのを期待しているからなのだろうか??
pollFirst()
public E pollFirst() {
final Object[] es;
final int h;
E e = elementAt(es = elements, h = head);
if (e != null) {
es[h] = null;
head = inc(h, es.length);
}
return e;
}
コードを読んでいると一旦定数に入れるのをよく見かける。
elementAt()にも一度定数に代入して渡しているがどうしてなんだろう。。
elementAt()は配列内の要素を取得するだけでes,hは変更されないのに。
java全体で一度定数に代入するのが推奨されているのだろうか、それともこれはコアだからより厳重にという意味合いなのだろうか。
size()
public int size() {
return sub(tail, head, elements.length);
}
subメソッド
static final int sub(int i, int j, int modulus) {
if ((i -= j) < 0) i += modulus;
return i;
}
これもスタティックメソッド。
やってることはシンプルでheadとtailの差分を求めている。
tailからheadを引いているがtailはint型つまりプリミティブ型だから元のメンバ変数は変更されない。
感想
まず要素を配列で保持しているのが予想外だった。
僕はキューの要素は連結リストみたいにノードとして繋がっていると学習していたためだ。
そして最大の疑問は大量にあるスタティックメソッドである。どうしてインスタンスメソッドじゃないんだ。
誰か知っている方いたら教えて頂きたいです。
またメソッドが思った以上に分割されているなとも感じた。
プライベートメソッドは多少長めのメソッドもあるがパブリックメソッドはほとんどが10行以内になっている。
普段は限られた人のコードしか読むことがないのでこうして他人のコードを読むことは非常に勉強になった。
Discussion
私も気になってちょっと調べてみました。
対象メソッドがインスタンス状態を変更しないと明示するためがしっくりしました。
StackOverflow