実装編②HashTable,JavaAPI

Presentation on theme: "実装編②HashTable,JavaAPI"— Presentation transcript:

1 実装編②HashTable,JavaAPI
サブゼミ第8回 実装編②HashTable,JavaAPI

2 Objective 連想配列（ハッシュテーブル）の概念を利点欠点を明らかにしながら説明できるようになる
ハッシュテーブルを使ったプログラムが書けるようになる JavaAPIを使ったプログラムが書けるようになる

3 前回のモデル ・配列を管理するクラスを導入したクラス図 このままでは追加と表示しかできません

4 検索するには ☆例えば、商品番号1055の価格が知りたい場合 番号=1001 商品名="コーラ" 価格=150
番号=1055 商品名="DDレモン" 価格=120 番号=1022 商品名="ソーダ" 価格=140 [1] [2] [3] [4] 配列を順繰りにたどって探す（リニアサーチ) しかし遅いO(N)

5 検索するには ☆例えば、商品番号1055の価格が知りたい場合 番号=1001 商品名="コーラ" 価格=150
番号=1022 商品名="ソーダ" 価格=140 番号=1055 商品名="DDレモン" 価格=120 [1] [2] [3] [4] 商品番号順にならんでいれば（バイナリサーチ) なかなか速いO(logN)

6 でも実用性がない ☆商品番号1055の価格が知りたい ということはあまりなく ☆DDレモンの価格が知りたい という使い方をしたい

7 商品名で検索する ☆例えば、DDレモンの価格が知りたい場合 番号=1001 商品名="コーラ" 価格=150
番号=1022 商品名="ソーダ" 価格=140 番号=1055 商品名="DDレモン" 価格=120 [1] [2] [3] [4] 配列を順繰りにたどって探す（リニアサーチ) しかし遅いO(N) ではどのように検索したらよいのか

8 どのように検索したら 速くなるのか 現状の問題点を整理しよう 早くするためのアイディアを考えよう

9 こんなのが欲しい list[0].getPrice() list[1].getPrice()
このような配列を 「連想配列」（ハッシュテーブル） といいます。 list["コーラ"].getPrice() list["DDレモン"].getPrice() perlなどでは標準でできる Javaでは、そのようなオブジェクト を作る

10 ハッシュテーブルを作るには まず、文字として扱っている間は、コンピュータでは検索できないので、何らかの数字に変換します。
インデックスシング、ハッシング 例えば、こんなやり方があります（詳しくは専門書を見て） 変換表 コ 98 コーラ　　　　→ － 103 ラ 67

11 大きい配列を作る！？ コーラ → 9810367 これをそのまま配列のインデックスにしようとすると、相当大きい 配列が必要
コーラ　　　　→ これをそのまま配列のインデックスにしようとすると、相当大きい 配列が必要 list[ ].getPrice() →現実的ではない

12 小さい配列で済むためには 1000要素の配列で済ませることを考える コーラ → 9810367 → 367
コーラ　　　　→ 　　　　→　　　　367 プログラムで →367と変換するには %1000 (1000で割ったあまりを求める)

13 ハッシュ関数 高速検索できるように、文字列から、一定範囲の数字を求める関数のこと
詳しくは「アルゴリズムとデータ構造」を見てみよう 今回の説明でのまずいところを発見しよう JavaではObjectクラスにhashcode()メソッドがあるので、どんなオブジェクトでも、簡単に求めることができます。

14 衝突が起こる 違うオブジェクトが同じハッシュ値になる可能性がある コーラ → 31256448 → 448
コーラ　　　　→ 　　　　→　　　　448 ソーダ　　　→ 　　　　→　　　　448

15 衝突回避① 空き番地法（線形探索） ソーダも入りたい！ ・・・・・
1 2 3 4 447 448 コーラ 449 ソーダ 500 DDレモン ・・・・・ もし計算されたアドレスにすでにデータが格納されていた場合 次のアドレスにデータを格納する。 次も格納されていたらさらに次のアドレスに格納しようとする 検索するときにはハッシュ値を求めた後、そのアドレスから 順に配列の中身をリニアサーチで調べる

16 空き番地法（線形探索）の問題点 クラスター化 →平方探索に変えると第２種クラスター化
1 2 3 4 5 6 7 8 9 10 11 12 13 →平方探索に変えると第２種クラスター化 →クラスター化を防ぐためにダブルハッシュ などの技法を使う必要あり

17 衝突回避② 分離連鎖法 ・・・・・ 衝突したら、そのアドレスからさらに連結リストを使ってデータを格納しておく方法
1 2 3 4 447 448 コーラ 449 500 ソーダ DDレモン ・・・・・ 衝突したら、そのアドレスからさらに連結リストを使ってデータを格納しておく方法 検索するときにはハッシュ値を求めた後、そのアドレスから 順に連結リストを使って調べる

18 ハッシュテーブルの 利点、欠点を考えてみよう

19 ハッシュテーブルの概念整理 key value 辞書、住所録みたいなものに 適している 青山 090-xxx-xxxxx 海保 高嶋 松澤
”コーラ” colaObject ”ソーダ” sodaObject ”お茶” chaObject ”DD” ddObject

20 ハッシュテーブルの問題点 データの保持に内部的には配列を使用するので 　事前に用意した配列が満杯に近づいてくると 　検索、挿入の効率が格段に落ちる 保持するデータを昇順や降順に 　ソートして取り出すといった機能はない 高速な検索が必要で確保するべきデータ量が ある程度予測できる場合に使う

21 JavaAPIを利用する API Application Programming Interface
アプリケーションを作るためによく使う機能を提供するプログラム →ライブラリ Javaでは関数群ではなく、よく使われるクラスの集まりと考えればよい Swingや、Servletなどもそれに当たります。

22 APIを使おう 配列で作ったリスト、連結リスト、ハッシュテーブルなどは良く使うので、 既に作られている。 配列で実装された リストクラス
連結リストで実装された リストクラス

23 APIを利用した設計

24 Listの使い方 特徴 主な実装クラス 主なメソッド データを順番に並べて格納する 格納するデータは重複してもかまわない
ArrayList･･･単方向リストを配列で実装したもの LinkedList・・・配列で実装した連結リスト 主なメソッド add(Object)・・・リストにオブジェクトを追加する get(int)･･･リストから引数の位置にある 　　　　　　　要素を取り出す remove(Object)･･･指定された要素を削除 size()･･･リストの要素数を返す iterator()･･･リストのIteratorを返す

25 使い方を調べる JavaAPIドキュメント
これを使えば知らない機能や 知らないクラスなども調べて使うことができます。 メソッドの使い方を忘れてしまったり、知らない機能を 追加したいときはまずAPIを見てみる癖をつけましょう！

26 Listを使った実装ー定義ー import java.util.*; public class 取扱商品型 {
private List 商品情報リスト;//取り扱う商品情報のリスト /** * コンストラクタ */ public 取扱商品型() { 商品情報リスト=new ArrayList();//ArrayListを初期化する }

27 Listを使った実装ー追加ー /** * 取扱商品に商品情報を追加するメソッド */
public void 商品追加(商品情報型 追加商品情報){ 商品情報リスト.add(追加商品情報); }

28 Listを使った実装ー検索ー /** * 商品を商品名で検索するメソッド */ public 商品情報型 検索(String 検索名){
//リニアサーチ！こんなプログラムは実際には書くなよ。-->Hashでね int len = 商品情報リスト.size(); for(int i=0;i<len;i++){ 商品情報型 商品情報 = (商品情報型)商品情報リスト.get(i); if(商品情報.get商品名().equals(検索名)){//見つかった return 商品情報; } return null;//見つからなかった

29 Listを使った実装ー表示ー /** * 登録されているすべての商品情報の商品名とID、価格を出力するメソッド */
　/** * 登録されているすべての商品情報の商品名とID、価格を出力するメソッド */ public void 商品表示(){ int len = 商品情報リスト.size(); for(int i=0;i<len;i++){ 商品情報型 商品情報 = (商品情報型)商品情報リスト.get(i); System.out.println(商品情報.get商品名()+" "+商品情報.get商品価格()+"円"); }

30 Collectionフレームワーク

31 今週の課題① APIドキュメントを読んで、 CollectionクラスとCollectionsクラスの違いを説明しなさい
JavaAPIを使ってソートする方法を調べなさい。そしてそのソートはどんなアルゴリズムを使っているか答えなさい スタック、キューを作るにはどのクラスをどんな風に使えばよいのか調べなさい

32 今週の課題② 先週配布したソースコードを 改良して取扱商品は HashMapを使い、取扱貨幣は ArrayListを使ってデータを 格納するように改良してください。 また取扱商品には検索()メソッドを 追加してください。 必ずHashMapのAPIを調べてから行うこと。

33 課題のために APIドキュメントとスケルトン（持ってない人は）ここからダウンロードも可能です

34 発展課題 HashMapのソースコードを読んで、 実装が、「空き番地法」「分離連鎖法」のどちらでなされているかを答えなさい。

35 冬休みの課題 自分の作るシステムをCUIベースのアプリケーションで完成させてください。
CUIができれば、Webアプリにするのはあとはそう難しくありません