サブゼミ第8回
実装編②HashTable,JavaAPI
Objective
連想配列（ハッシュテーブル）の概念を利
点欠点を明らかにしながら説明できるよう
になる
ハッシュテーブルを使ったプログラムが書
けるようになる
JavaAPIを使ったプログラムが書けるよう
になる
前回のモデル
・配列を管理するクラスを導入したクラス図
このままでは追加と表示しかできません
検索するには
☆例えば、商品番号1055の価格が知りたい場合
番号=1001
商品名="コーラ"
価格=150
番号=1055
商品名="DDレモン"
価格=120
番号=1022
商品名="ソーダ"
価格=140
[1]
[2]
[3]
配列を順繰りにたどって探す（リニアサーチ)
しかし遅いO(N)
[4]
検索するには
☆例えば、商品番号1055の価格が知りたい場合
番号=1001
商品名="コーラ"
価格=150
番号=1022
商品名="ソーダ"
価格=140
番号=1055
商品名="DDレモン"
価格=120
[1]
[2]
[3]
商品番号順にならんでいれば（バイナリサーチ)
なかなか速いO(logN)
[4]
でも実用性がない
☆商品番号1055の価格が知りたい
ということはあまりなく
☆DDレモンの価格が知りたい
という使い方をしたい
商品名で検索する
☆例えば、DDレモンの価格が知りたい場合
番号=1001
商品名="コーラ"
価格=150
番号=1022
商品名="ソーダ"
価格=140
番号=1055
商品名="DDレモン"
価格=120
[1]
[2]
[3]
配列を順繰りにたどって探す（リニアサーチ)
しかし遅いO(N)
ではどのように検索したらよいのか
[4]
どのように検索したら
速くなるのか
現状の問題点を整理しよう
早くするためのアイディアを考えよう
こんなのが欲しい
list[0].getPrice()
list[1].getPrice()
list["コーラ"].getPrice()
list["DDレモン"].getPrice()
このような配列を
「連想配列」（ハッシュテーブル）
といいます。
perlなどでは標準でできる
Javaでは、そのようなオブジェクト
を作る
ハッシュテーブルを作るには
まず、文字として扱っている間は、コン
ピュータでは検索できないので、何らかの
数字に変換します。
インデックスシング、ハッシング
例えば、こんなやり方があります（詳しくは専門書を見て）
変換表
コ 98
－ 103
ラ 67
コーラ
→
9810367
大きい配列を作る！？
コーラ
→
9810367
これをそのまま配列のインデックスにしようとすると、相当大きい
配列が必要
list[9810367].getPrice()
→現実的ではない
小さい配列で済むためには
1000要素の配列で済ませることを考える
コーラ
→
9810367
→
367
プログラムで9810367→367と変換するには
9810367%1000
(1000で割ったあまりを求める)
ハッシュ関数
高速検索できるように、文字列から、一定
範囲の数字を求める関数のこと
詳しくは「アルゴリズムとデータ構造」を見てみ
よう
今回の説明でのまずいところを発見しよう
JavaではObjectクラスにhashcode()メソッ
ドがあるので、どんなオブジェクトでも、簡
単に求めることができます。
衝突が起こる
違うオブジェクトが同じハッシュ値になる可
能性がある
コーラ
ソーダ
→
→
31256448
587648448
→
→
448
448
衝突回避①
空き番地法（線形探索）
1
2
3
4
ソーダも入りた
い！
447
・・・・・
448
コーラ
449
ソーダ
500
DDレモン
もし計算されたアドレスにすでにデータが格納されていた場合
次のアドレスにデータを格納する。
次も格納されていたらさらに次のアドレスに格納しようとする
検索するときにはハッシュ値を求めた後、そのアドレスから
順に配列の中身をリニアサーチで調べる
空き番地法（線形探索）の問題点
クラスター化
1
2
3
4
→平方探索に変えると第２種クラスター化
→クラスター化を防ぐためにダブルハッシュ
などの技法を使う必要あり
5
6
7
8
9
10
11
12
13
衝突回避②
分離連鎖法
1
2
3
4
447
・・・・・
448 コーラ
ソーダ
DDレモン
449
500
衝突したら、そのアドレスからさらに連結リストを使ってデータを
格納しておく方法
検索するときにはハッシュ値を求めた後、そのアドレスから
順に連結リストを使って調べる
ハッシュテーブルの
利点、欠点を考えてみよう
ハッシュテーブルの概念整理
key
”コーラ”
”ソー
ダ”
”お茶”
”DD”
value
辞書、住所録みたいなものに
colaObject
sodaObject
chaObject
ddObject
適している
青山
090-xxx-xxxxx
海保
090-xxx-xxxxx
高嶋
090-xxx-xxxxx
松澤
070-xxx-xxxxx
ハッシュテーブルの問題点
•データの保持に内部的には配列を使用するので
事前に用意した配列が満杯に近づいてくると
検索、挿入の効率が格段に落ちる
•保持するデータを昇順や降順に
ソートして取り出すといった機能はない
高速な検索が必要で確保するべきデータ量が
ある程度予測できる場合に使う
JavaAPIを利用する
API
Application Programming Interface
アプリケーションを作るためによく使う機能を提供するプログラム
→ライブラリ
Javaでは関数群ではなく、よく使われるクラスの集まりと考えればよい
Swingや、Servletなどもそれに当たります。
APIを使おう
配列で作ったリスト、連結リスト、ハッシュテーブルなどは良く使うので、
既に作られている。
List
ArrayList
配列で実装された
リストクラス
LinkedList
連結リストで実装された
リストクラス
APIを利用した設計
自動販売機
<<クラス図>>
商品情報型
- 商品名 : String
- 商品情報ID : int
- 価格 : int
取扱商品型
+ 商品追加()
+ 商品表示() 1
+ 検索()
VendingMachine
Appli
0..n + get価格()
+ get商品情報ID()
+ get商品名()
ArrayList
(java.util から)
取扱貨幣型
+ 貨幣追加()
+ 貨幣表示() 1
貨幣情報型
- 貨幣情報ID : int
- 価値 : int
0..n + get価値()
+ get貨幣情報ID()
Listの使い方
特徴
データを順番に並べて格納する
格納するデータは重複してもかまわない
主な実装クラス ArrayList･･･単方向リストを配列で実装したもの
LinkedList・・・配列で実装した連結リスト
主なメソッド
add(Object)・・・リストにオブジェクトを追加する
get(int)･･･リストから引数の位置にある
要素を取り出す
remove(Object)･･･指定された要素を削除
size()･･･リストの要素数を返す
iterator()･･･リストのIteratorを返す
使い方を調べる
JavaAPIドキュメント
Javaが提供する多くのクラスとその属性や操作を一つにまとめた
マニュアルのようなもの。
これを使えば知らない機能や
知らないクラスなども調べて使うことができます。
メソッドの使い方を忘れてしまったり、知らない機能を
追加したいときはまずAPIを見てみる癖をつけましょう！
http://java.sun.com/j2se/1.3/ja/docs/ja/api/index.html
Listを使った実装ー定義ー
import java.util.*;
public class 取扱商品型 {
private List 商品情報リスト;//取り扱う商品情報のリスト
/**
* コンストラクタ
*/
public 取扱商品型() {
商品情報リスト=new ArrayList();//ArrayListを初期化する
}
Listを使った実装ー追加ー
/**
* 取扱商品に商品情報を追加するメソッド
*/
public void 商品追加(商品情報型 追加商品情報){
商品情報リスト.add(追加商品情報);
}
Listを使った実装ー検索ー
/**
* 商品を商品名で検索するメソッド
*/
public 商品情報型 検索(String 検索名){
//リニアサーチ！こんなプログラムは実際には書くなよ。-->Hashでね
int len = 商品情報リスト.size();
for(int i=0;i<len;i++){
商品情報型 商品情報 = (商品情報型)商品情報リスト.get(i);
if(商品情報.get商品名().equals(検索名)){//見つかった
return 商品情報;
}
}
return null;//見つからなかった
}
Listを使った実装ー表示ー
/**
* 登録されているすべての商品情報の商品名とID、価格を出力するメソッド
*/
public void 商品表示(){
int len = 商品情報リスト.size();
for(int i=0;i<len;i++){
商品情報型 商品情報 = (商品情報型)商品情報リスト.get(i);
System.out.println(商品情報.get商品名()+" "+商品情報.get商品価格()+"円");
}
}
Collectionフレームワーク
java.utilパッケージの
クラス図
Collection
List
ArrayList
Set
LinkedList
SortedSet
Map
HashSet
HashMap
TreeMap
今週の課題①
APIドキュメントを読んで、
CollectionクラスとCollectionsクラスの違いを
説明しなさい
JavaAPIを使ってソートする方法を調べなさい。
そしてそのソートはどんなアルゴリズムを使っ
ているか答えなさい
スタック、キューを作るにはどのクラスをどん
な風に使えばよいのか調べなさい
今週の課題②
先週配布したソースコードを
改良して取扱商品は
HashMapを使い、取扱貨幣は
ArrayListを使ってデータを
格納するように改良してください。
また取扱商品には検索()メソッドを
追加してください。
必ずHashMapのAPIを調べてから行うこと。
課題のために
APIドキュメントとスケルトン（持ってない人
は）ここからダウンロードも可能です
http://nautilus.crew.sfc.keio.ac.jp/seminar/2001fall2/sub8/
発展課題
HashMapのソースコードを読んで、
実装が、「空き番地法」「分離連鎖法」のど
ちらでなされているかを答えなさい。
冬休みの課題
自分の作るシステムをCUIベースのアプリ
ケーションで完成させてください。
自動販売機CUIバージョンをメールで送ります
ので参考にして下さい
CUIができれば、Webアプリにするのはあとは
そう難しくありません
© Copyright 2024 ExpyDoc
