Help us understand the problem. What is going on with this article?

ハッシュテーブルと二分木について調べたこと

More than 1 year has passed since last update.

はじめに

ハッシュテーブルと二分木について、色々と調べたのでまとめた。

アルゴリズム関連では、以下の記事も参考にしてください。
①計算量とソートの基本
②実用的なソート
③探索
④再帰関数

ハッシュテーブルと二分木ってなに?

ハッシュテーブル(hash table)

ハッシュテーブルはm個の要素を格納できる配列T(画像でいうと、hashes)と、データのキーを決定するハッシュ関数(hash functions)から構成されます。

ハッシュ関数へ入力するキーは整数である必要があるため、キーが文字列である場合は対応する整数へ変換する必要があります。

例えば、ハッシュ関数として$h(k)=k~mod~m$などを用いることができます。
ただ異なるキーが同じハッシュ値となる衝突が起きる可能性があるので、それを解決する方法が二つあります。

  1. オープンアドレス法
  2. チェイン法

英語のwikipediaにわかりやすい説明が載っていたので、そちらを参考にしてください。

1のチェイン法は、衝突を起こしたキー同士を連結リストで繋いで格納する方法です。

2のオープンアドレス法は衝突が起きると、テーブルの中で空いている別の位置を探す方法で、ハッシュ関数とは別のハッシュ関数を用いて、次の位置を探していきます。

ハッシュテーブルにおいては、衝突が起きなければ$O(1)$で挿入や探索を行うことができます。

参考

What is a HashTable Data Structure - Introduction to Hash Tables , Part 0 - YouTube
ハッシュ法

二分木(binary tree)

二分木とは根付きの木構造で、ノードの持つこの数が高々2であるものを指します。
計算量が常に$logn$になるというのが特徴です。

  • ハッシュテーブほどメモリの確保が要らない。
  • ハッシュ関数を考えずに、済む。

などのメリットがあります。
ただ木のバランスが取れておらず、片方が長くなると、計算量は$O(n)$に近づくため、左右のバランスをとる平衡木などが考案されています。回転、などの手法によって実現されます。

参考

wantedly
「シゴトでココロオドル」ためのビジネスSNS「Wantedly」の開発・運営をしています。
https://wantedlyinc.com/ja/presentations
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした