脳log[2009-07]

♪ [買] ぺんてる グラフギア1000 0.5mm

今まで、軽い安い細い短いを基準に 100-200円のを使ってたんだけど、シンプルで寸胴なのがかえって見つからなかったりもする。今回初めてちょっと色気を出してみた。

グラフギア1000 0.5

Pentel
￥ 750

ペン先収納機能と大きなクリップが決め手。グリップのイボイボもアクセントとして気に入ってるので、0.5mmの灰色のゴムはすこし地味にすぎる。

唯一にして最大のネックは重さと重心の高さ。ペン先を持って振ってみればいかに頭が重たいか実感できる。長時間の使用には向かないだろうが、そうでなければ満足の品。

あ、素材が真鍮、アルミ、鉄、ステンレスだ。錆びるんじゃなかろうか。

 対抗馬1:

三菱鉛筆 uni SHIFT(シフト)0.5mm【シルバー&ブルー】 M5-1010 26 SV

三菱鉛筆
￥ 950
こちらもペン先収納。グラフギアのようなダブルノックではなく、ねじるのでもなく、押して回すことでペン先を固定するのが意外に手間。ペン先を収納したときに解放されるグリップのゆるゆる感も頼りない。クリップが小さい。

 対抗馬2

グラフ1000(PG1005)

ぺんてる
￥ 910
ペン先は収納できず、クリップは極小。だが軽い。一番無難で実用的なのだが面白味に欠ける。

 対抗馬3

シャープペン「クルトガ」ハイグレードタイプ　0.5mm【ブラック】 M5-1012

三菱鉛筆
￥ 945

面白そうではある。クルトガを実現するために芯が 0.3mm引っ込むのに違和感を覚えるとの声多数。だが慣れるとも聞く。もう一本買うならこれだがシャーペンは一本で十分。

最終更新: 2009-08-23T05:42+0900

♪ > ５００円弱の弱ってどう言う意味？ - Yahoo!知恵袋

５００円弱の弱ってどう言う意味？

例えば、５００円弱って言う場合は、４９０円（５００円より若干少ない）ですか？ それとも５１０円（５００円より若干多い）ですか？ 前者だとばかりずっと思っていましたが、知人は後者だと思ってたそうです。

国語大辞典によれば、ある数の端数を切り上げたとき、示す数よりは少し、不足があることをいうために、数字のあとに弱を付けて用いる。「一万円弱」。

とあります。ですから、後者が正解ですね。

最近、通じてないな、と感じた経験がある。相手がこの言い方を知らないのならその場で言い換えるチャンスもあるけど、○○弱といったとき○○だけあるのかないのか、という部分をさらっと勘違いされていた。

回答をひとつだけ取り上げたけど、辞典を引いてさえ後者といわれては言葉がない。490円をきりのいい 500円に切り上げる、でも実際の金額がそれより少ないことを示すために弱をくっつけて 500円弱という、んじゃないの。辞典が示してるのは前者でしょ。

500円弱を「500円より少し上」に割り当ててしまったら 500円強の行き場は？「500円より大幅に上」とか？聞いてみたい。

最終更新: 2009-08-25T02:45+0900

♪ [正規表現][Firefox] XRegExp-1.0.1と Firefoxの /(?!)/

20090628p01で書いた Firefoxのバグっぽいものが XRegExpに影響するみたい。

// Firefox 3.0.11 + XRegExp 1.0.1 での実行結果
alert( XRegExp("[]").test("a") ); //=> true
alert(  RegExp("[]").test("a") ); //=> false

[] と [^] の意味するところってなんでしょうね。[] は空の文字集合だから「どれでもない一文字」とマッチする(=空文字列にもマッチせず必ず失敗する)。[^] は空の文字集合の補集合だから「任意の一文字」だろうか。

参考ページを見つけた > 文字クラス(http://suika.fam.cx)

結局、こういうことだ。

• 主要 4ブラウザのうち [] と [^] が使えないのは IEだけ。
• Opera(9.61)は [] と [^] がおかしい(他と違う)。
• Firefox(3.0.11, 3.5RC3)は (?!) と (?=) がおかしい(他と違うし、自分自身の (?!|)、(?=|) とも違う)。

(IEの件を除いて)どのパターンも規格上の正解やデファクトスタンダードがなくて混乱してんじゃないかなあ。こういうのには近づかないに限る。

 追記@2009-07-04 04:44: 内容確認。

正しくコメントが読めてるといいんだけど……。

IEが空の文字セット [] を処理しないのは(ECMAScriptの仕様をすっとばして) Perlその他、JavaScript以外の多くの実装にならっているもので、[ に続く最初の文字を文字通りの文字 ] だとしているから。だから []] は [\]] と同じ意味になる。

Firefoxで (?!) の代わりに (?!|)、(?=) の代わりに (?=|) を使うのは良くなくて、つまりこれらの結果は同じになるべきだけど、どちらになるかは将来の Firefox次第だから。バックトラックの発生にもつながって効率的にも不利。だから (?!) の代わりは \b\B。(?=) の代わりは (?:) が良い。

\b\B というのは覚えておこう。

 追記@2009-07-04: はずしてた。

冒頭の指摘ははずしてる。考える前に、気付いたことをただ書いたせいだ。

XRegExpの目的の一つは、ブラウザごとにまちまちな挙動を見せる JavaScriptの正規表現に関するメソッドを仕様に準拠させることだったと思う(String.split()とか RegExp.lastIndexとか)。

だから空の文字セット( [] と [^] )を提供する第一の目的は 5ブラウザ(IE, Fx, Opera, Safari, Google Chrome)のうち不当にこれを受け付けない IEにおいて、仕様で許された正規表現パターンを利用可能にすること、かもしれない。

その過程で、Firefoxがネイティブに処理する空の文字セットと、XRegExpの提供する空の文字セットの挙動が食い違ってしまっている(1行目 1、2列)、というのが冒頭の指摘。でもこれは重要ではないし、同様の指摘を Operaについても行うことができる(3行目 1、2列と 3、4列)。

そうではなくて、ライブラリ利用者として「仕様に準拠した」「ブラウザ間で統一された」機能を望む視点から、XRegExpの提供する空の文字セットが Firefoxにおいてのみ違う意味になること(2列目)をこそ指摘すべきだった。(実際そうしたんだけど、日記の内容だけが古かったのでこうして追記している)

 すごくおかしな Firefox(3.0.11)の (?!)

全てのパターンに (?!) が含まれているから、本当は全て falseになってほしい。

/(?!)/.test("abc")     //=> true！
/(?!)(?!)/.test("abc") //=> false

/^(?!)/.test("abc")    //=> false
/(?!)$/.test("abc")    //=> true！

/a(?!)/.test("abc")    //=> false
/(?!)a/.test("abc")    //=> true！

/\b(?!)/.test("abc")   //=> false
/(?!)\b/.test("abc")   //=> true！

/(?:)(?!)/.test("abc") //=> true！
/(?!)(?:)/.test("abc") //=> true！

(?!) が実質的にパターンの先頭にあるときだけ、存在しないかのように振る舞っているような。すごく限定された状況でのみ発動するんだったんだ。

ここまで書いてなかったことに気付いたけど、これが XRegExp("[]") に影響するのはこのパターンが内部的に (?!) に書き換えられるから。XRegExp (1.1.0, 2009-07-04)では \b\B に置き換えられるようになっていて、Firefoxのおかしな挙動に影響されて他のブラウザと違う結果になることはなくなっている。

もう書かれてた！ > http://blog.stevenlevithan.com/archives/xregexp-1-0/comment-page-1#comment-37653

 追記@2009-07-05 04:40: XRegExp-1.0の設計の良さを示す好例 > 20090703c02

自身の機能を XRegExp.addToken()で提供しており、ユーザーも同じ方法で拡張できる。トークンの有効範囲が文字セット [……] の内か外か、その両方かは addToken()の第3引数のビットフラグ( XRegExp.INSIDE_CLASS, XRegExp.OUTSIDE_CLASS )で指定できるし、エスケープシークェンスは予め処理されているので \(?!) を \\b\B に置き換えてしまう心配もない。簡単でしょう。

でも鬼車の \g を追加しようとして、名前付きキャプチャ内部のパターンを手に入れられず、中断。

 追記@2009-07-05 04:40: \gの実装サンプルを見てみた。

その \gの利用例が次。

XRegExp("(?<any_backref>\\3|\\4){0}     \
         (?<smiles>(?::-[D)])+){0}      \
         ([ab]) ([12]) \\g<any_backref>+\
         \\g<smiles>                    ", "x").test("a22aaa:-):-D"); // true

解説すると、まず名前付きキャプチャを使って再利用を前提としたパターンを定義する(any_backrefと smiles)。ポイントは量指定子{0}の存在で、現状ではこれが必ず必要になる。これによりこの名前付きキャプチャはマッチに参加せず、一文字も消費せずに成功する。その存在意義は \g<smiles> のように、後で名前を使ってパターンを再利用できること。

上の例で、実際に文字を消費するパターンは後半分、次の部分だけ。

    /([ab])([12])\g<any_backref>+\g<smiles>/

Rubyで同じ意図を持って書くとこういうふうになる。

irb> any_backref = /\1|\2/
=> /\1|\2/
irb> smiles = /(?::-[D)])+/
=> /(?::-[D)])+/
irb> re = /([ab])([12])#{any_backref}+#{smiles}/
=> /([ab])([12])(?-mix:\1|\2)+(?-mix:(?::-[D)])+)/
irb> re.match( "a22aaa:-):-D" ).to_a
=> ["a22aaa:-):-D", "a", "2"]

さて、パターンの再利用が \g の利用法だけど、個人的にそれが最大の効果を発揮するのは、パターン定義の中でパターンを呼び出したとき、再帰的なパターンを定義できることだと思っている。20080111p01で既に書いているが、

 /%[Qq]?(?<brace>\{[^\{}]*(?:\g<brace>[^\{}]*)*})/

名前付きキャプチャ (?<brace>……) の中に \g<brace> がある。こういう GNUの命名のような再帰的定義ができてこそ \g を利用する価値があると個人的には思う。

addToken()で \g を定義する方法として考えていたのは「パターン文字列を、上限を決めて再帰的に展開する」というもの。このように。

1. (?<brace>{\g<brace>})
2. (?<brace>{(?:{\g<brace>})})
3. (?<brace>{(?:{(?:{(?:{\g<brace>})}))})
4. (?<brace>{(?:{(?:{(?:{(?:)})}))})

実際の手順は addTokenの第二引数が文字列を返す代わりに toString()を定義したオブジェクトを返し、xregexp.jsの下の引用部分、output.join("") の時点で、名前付きキャプチャ内のパターンを参照してパターン文字列を返そうというもの。

            regex = RegExp(output.join(""), real.replace.call(flags, /[^gimy]+/g, ""));
            regex._xregexp = {
                source:       pattern,

コードの枠組みはこんなの。もちろんこのままでは動かない。

function PatternOfNamedCapture(name) {
	this.name = name;
}
PatternOfNamedCapture.prototype.toString = function(){
	// ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
	if(MAX_RECURSION < count++) {
		return "(?:)";
	} else {
		return output.slice(
			defs[this.name].start,
			defs[this.name].end
		).join("");
	}
	// ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑
};
XRegExp.addToken(
	/\\g<([$\w]+)>/,
	function(match) {
		return new PatternOfNamedCapture(match[1]);
	}
);

♪ [tDiary] makerss.rb: 更新したつもりのないエントリまでが上がってくる理由。

ある日のエントリの一つを更新すると、同じ日の他のエントリまでが更新されたとして上がってくる理由。たぶんそれまでに他のエントリで「ちょっとした修正」を行っていたのだろう。makerss.rbを見てみたら

add_update_proc do
	makerss_update unless @cgi.params['makerss_update'][0] == 'false'
end

ちょっとした修正では日記の更新時に何も行っていない。これを、index.rdfの更新はしないけど cache/makerss.cacheの更新はする、というふうに変えられないだろうか。

目的は、以前に加えたちょっとした修正と、今回の普通の更新で加えた変更とを区別するため。

編集対象のセクションを特定できるなら、cache/makerss.cacheを常に更新することで、以前のちょっとした修正を検出しなくなるようにする必要はないし、むしろ LDRのようにフィードの内容の一字一字を比較するリーダー?(フィードアグリゲータ?)まで騙すことを考えると、cache/makerss.cacheの内容はちょっとした修正以前の古いままにしておく方がいいみたい。

じゃあ、なぜ既にセクション単位で編集を行ってるこの日記で、直前の編集に関係していないセクションまでが上がってくるのか？ makerss.rbの変更まで手を回す前にやる気が尽きたから。

update_procに引数の追加が必要なんだけど、改めて具体的に考えてみると単純にセクションナンバー1つを渡せばよいというものでもなさそうだ。セクション2を編集した結果、セクション2がなくなってセクション3が 2に繰り上がってる可能性がある。セクション2が分裂してセクション2と 3になってる可能性がある。

LDRといい update_procの引数といい、万全を期すと二進も三進もいかんなあ。(LDRは使ってないから外せない問題ではないし、update_procは {before=>2, after=>2..3} を渡すだけで済んでしまう気もするけど)

ああ、afterの範囲を確定するのが難しいんだ。変更前に、編集対象のセクションの前にいくつ、後にいくつのセクションがあるかを数えておく手があるけど、場合によったら直前のセクションと結合してしまうことがあるからなあ(セクション2を編集していたはずが、セクション2を削除してセクション1に追記したことになってる可能性がある)。この場合セクション1に変更があったことは無視してセクション2が削除されたことだけを考えていいなら、やっぱり前後のセクション数を数えておく方法でよさそうだ。

makerss.cacheは二つの目的を持ってるんじゃないか。変更のあったセクションを検出する目的と *.rdfのソースにする目的。

そもそも、*.rdfのソースは *.rdf自身で十分じゃないか？(深くわかってるわけじゃないけど) これに変更のあったセクションを特定できる引数が update_procに加わったら makerss.cacheを用済みにできないか。

できない。一日単位の編集機能をなくせるわけじゃないから今と同等の変更検出機能は必要。そうすると *.rdfのソースを makerss.cacheから *.rdfにスイッチする必要もなさそうに思えるけど、……ないかも。(うっかりフィードに紛れ込んだテストコメントは index.rdfからアイテムを削除するのでなく、コメントを非表示にすれば、あとあと甦ってくることもなかったんだ)

 整理。

makerss.cacheは二つの役割を持っている。

• 変更のあったセクションを検出する。
• .rdfのソースにする。

変更のあったセクションの検出能力に難があったので改善を試みる。一日単位の編集機能が存在し続け、rdfのエントリの単位がセクションである限り、変更のあったセクションの検出能力の向上は無駄にならない。

makerss.cacheの日記内容をちょっとした修正でも更新する。

これでちょっとした修正のあったセクションの誤検出はなくなる。だがこの makerss.cacheをもとに *.rdfを作成するとエントリの内容がちょっとした修正後のものになり、LDRなど RSSリーダーによる過剰検知の原因となる。

*.rdfのソースを *.rdfにする。

右から左に流すだけでは過剰検知の起こりようがない。フィードを更新するときにどんな問題が発生するだろう……。手順を考える。

1. makerss.cacheとの比較を基に、追加、変更のあったセクションを特定する。
2. .rdf内のエントリから削除された(現在のセクション数から考えられるより大きいセクションナンバーを持つ)セクションを取り除く。
3. 追加、変更されたセクションを .rdfのエントリに変換する。
4. .rdf内に対応するエントリがあれば上書き、なければ追加し、.rdfの先頭に移動する。
5. エントリ数の上限まで書き込み。

問題は、フィードに含まれる日記やコメントを隠したりセクションを削除したりするとエントリ数が上限より少なくなる、だけだろうか。最初は無理そうに思えたけど、なんだったんだろう。

makerss.cacheから読み込んだものと *.rdfから読み込んだものとは Rubyオブジェクトか文字列かという違いがあるんだなあ。でもそれが意味を持つのは MakeRssNoComments#itemで呼ばれる rdfsec.section.respond_to?( :body_to_html )だけみたいだから、ここを rdfsec.id.index("p") に置き換えれば *.rdfから読み込んだ xml文字列だけで makerss.cacheの代わりができそう。

 整理(Plan B)

セクション単位の編集機能があり、makerss.rbが update_procの引数から変更のあったセクションを知ることができれば、今以上の、変更のあったセクション検出能力は特段必要ではない。

makerss.cacheはこれまで通りちょっとした修正では更新されず、LDRをちょっとした修正以前の古い内容でだまし続けることが可能。

日記の書き手はフィードの更新を伴うデリケートな編集作業ではセクション単位の編集を行うことで、余計なセクションが上ってくることを避けられる。

こっちが断然楽そうだ。でも自分の環境で閉じてしまうから代替案なんだよね。

タイトル(脳log)にふさわしい垂れ流しっぷりじゃあないですか？

 をを、バグってる

はるか上の方でこう書いた。

場合によったら直前のセクションと結合してしまうことがあるからなあ(セクション2を編集していたはずが、セクション2を削除してセクション1に追記したことになってる可能性がある)。

何を見て書いていたかというと……

	unless body1.empty?
		current_section = @sections.pop
		if current_section then
			body1 = "#{current_section.body.sub( /\n+\Z/, '' )}\n\n#{body1}"
		end
		@sections << WikiSection::new( body1, author )
	end

解説解説

appendされた Wikiソースがサブタイトルを持っていないもの( body1 )だったら、
最後のセクションを取り除き

最後のセクションの本文( current_section.body, サブタイトルを含まない )と body1を連結し、

新しいセクション( サブタイトルなし )として追加する。

WikiSection#bodyの代わりに WikiSection#to_srcを使わないとサブタイトルが消えてしまう。

			body1 = "#{current_section.to_src.sub( /\n+\Z/, '' )}\n\n#{body1}"

サブタイトルのあるセクションに、サブタイトルのない本文を追加したときに、サブタイトルのないセクションができあがるのを防ぎます > fix_and_test_append_without_subtitle.diff

 Plan B 仮実行中

セクション単位の編集機能が追加されていることが前提。そのせいでこの日記でしか使えないから気乗りしなかったんだけど、第一案が手詰まりなのと一つの実験場として可能性を示すために。

update_procに updated_sectionというパラメータを追加し、makerss.rbが過去のちょっとした修正を誤検出するのを防ぎます > add_param_updated_section_to_update_proc.diff

最終更新: 2010-01-15T21:38+0900

♪ [本] 自炊というらしい

ここは自炊技術のためのウィキです。
「自炊」とは2ちゃんねるが由来の隠語で、
「自分で漫画や雑誌、書物などを電子化する」という意味です。
2ちゃんねるの関連スレッドを読みたい方はダウンロード板へどうぞ。
初めての方は、左のメニューバー「事前準備」から下へ読んでください。
一流の職人になれるよう頑張りましょう。

日本全国でどれだけの人手が浪費されているのか。あまりにあほらしいので絶対に自炊はしません。「本」としての価値がある本と、電子データだけを買いたい。

♪ [Amazon][tDiary][Ruby] 徒労。劣化コピー。amazon.rb差し替え。SecretKey埋め込みなのでパーミッションは rw-------。

先人 > Amazon Product Advertising APIの認証の件 - zorioの日記

Ruby-1.8.7と Ruby-1.8.6では String#force_encoding("ASCII-8BIT")ができず、String#ordもない(ないのはエンコーディングの概念がないからと、String#[]で代替できるからだと思われる)。それらを使い分けるために 2種類のメソッドを用意するくらいなら、unpackで配列経由でいいです。

require 'digest/sha2'
def hmac_sha256(key, message)
	hash = Digest::SHA256
	hash_block_size = 64 # bytes (= hash.new.block_length)
	key = hash.digest( key ) if hash_block_size < (key.bytesize rescue key.size)
	ikey = Array.new( hash_block_size, 0x36 )
	okey = Array.new( hash_block_size, 0x5c )
	key.unpack("C*").each_with_index{|key_byte, i|
		ikey[i] ^= key_byte
		okey[i] ^= key_byte
	}
	inner_hash = hash.new.update( ikey.pack("C*") )
	outer_hash = hash.new.update( okey.pack("C*") )
	digest = outer_hash.update( inner_hash.update( message ).digest ).digest
	return digest
end

短い秘密鍵は 0を補うって書いてあった。その処理が見あたらないのになぜうまくいくのかと考えたら、0を相手に排他的論理和をとったって何も変わらないのねん。

class Digest::Base

update(str)

self << str

文字列を追加する。self を返す。複数回updateを呼ぶことは文字列を連結してupdateを呼ぶことと等しい。すなわち m.update(a); m.update(b) は m.update(a + b) と、 m << a << b は m << a + b とそれぞれ等価である。

Ruby-1.9で文字列の連結は怖いので m.update(a + b) と m << a + b と Digest::SHA256.digest(ipad + message) は避けたい。

302 Foundはわかる。リバースプロキシは何するもの？

 追記@2009-08-04: 他の部分も

require 'uri'
require 'base64'
def amazon_authenticated_query_string( host, params )
	re_rfc3986_unreserved = /[^A-Za-z0-9\-_.~]/
	query_string = params.to_a.sort_by{|x| x.first }.map{|key, value|
		URI.encode(key, re_rfc3986_unreserved) +'='+ URI.encode(value, re_rfc3986_unreserved)
	}.join("&")
	string_to_sign = <<-"STRING_TO_SIGN".gsub(/^\t\t/, '').chomp
		GET
		#{host.downcase}
		/onca/xml
		#{query_string}
	STRING_TO_SIGN
	amazon_secret_access_key = "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"
	signature = Base64.encode64( hmac_sha256( amazon_secret_access_key, string_to_sign ) ).chomp
	return "#{query_string}&Signature=#{URI.encode(signature, re_rfc3986_unreserved)}"
end

最終更新: 2010-01-15T21:38+0900

♪ [Ruby][C++] 釣られますた

C/C++ではもちろん0==false はtrueなわけですが・・・ もしかして、boolean型を整数型とキャスト比較しない仕様なんでしょうか？

この辺はC/C++も難しくて 本質的には 2==trueも本当は真なんですが偽になったりもします。

Rubyでビットフラグをチェックするときは 0との比較を忘れてはいけない。

if(flag & mask)
  # (意図に反して)必ず実行される
end
if(0 != flag & mask)
  # 期待通り
end

というのはさておき、2==true に関して、「本質的には」という言葉が胡散臭い。その「本質」を表すコードは「(2!=false) == (true!=false)」であって、2==true は関係ないのでは？ ==は真偽値を返す演算子ではあっても、真偽値のみをオペランドにとる演算子ではないから、2==true も 1==true も -1==true までもが暗黙にそのように解釈されて真になったりしたら、むしろ気持ち悪い。それは PHPの世界だ。(偏見)

Cと逆だな

Rubyでは非0が偽だと言いたげですね。

 @2009-11-06 まさしく偏見でした。

Safe Bool (ja.wikibooks.org)という C++のイディオムがあって、つまり裏を返すと、危険な Boolean変換が C++には存在するということだ。やーめーてー。

C++09(予定)では explicitなコンストラクタみたいに、明示的なキャストを必要とする変換を定義できるようになるらしい。

♪ クイズ。> 本当はむずかしいハッシュテーブル - sumiiの日記

ネタバレ注意！

member()があっさり 0 を返しすぎるのはすぐわかった。コメント欄の、ハッシュ表があふれることを否定しない表現「『要素の個数はハッシュ表のサイズBより小さいとする』という前提なので、『全部埋まっていたら』の意味にもよりますが」を読んでいて、前提条件に関わらず、同じ要素が複数回 insert()されるとハッシュ表があふれるのもわかった。さて 3つめは？ そして修正版は？

(member()相当の機能が欲しいだけなら)ソート済みの int配列にすれば…… < ハッシュテーブルじゃない！

意外にできる子とはいえ insert()と delete()でのメモリブロックの移動コストが気になる。一定サイズの配列(Chunk)をリストで管理したら……とかどうでもいい。

(元記事コメントから)> 削除済みマークを付ける

delete()で EMPTY(0)にせず DELETED(-1とか)にするのね。clear()するまで不良資産(DELETEDな要素)は貯まる一方、というわけでもなく、insert()するときに再利用できそうだ。

これ(削除済みマークを付ける)って FAじゃないのかなあ。

とりあえず、気付いた 2つの問題(delete()がからむと member()が不正確。重複要素であふれる)に対処した insert()はこう。EMPTYな要素より DELETEDな要素を優先して使用したくてフラグっぽい変数が増えてしまった。

/* 要素xをハッシュ表hに追加 */
void insert(int x) {
  int i = hash(x);
  int j = -1; /* i より優先して xを代入すべき位置 */
  while (h[i] != EMPTY) {
    if (h[i] == x) {
      /* return; */
      j = i;
      break;
    } else if (h[i] == DELETED) {
      j = i;
    }
    i = (i + 1) % B;
  }
  h[j != -1 ? j : i] = x;
}

delete()の方も、EMPTYの代わりに DELETEDを代入するように変更する。

重複要素でハッシュ表があふれることがなくなったとはいっても、insert()と delete()を繰り返すうちに DELETEDな要素が増えていって EMPTY要素の数が 0になる可能性はないだろうか。EMPTY要素がなくなると、存在しない要素xを引数にした member()が無限ループに陥る。直観的にそういう可能性はない気がするけど……。

完全ハッシュ関数の状態からスタートしよう。ハッシュテーブルには最低でも一か所の穴(どの要素xも配置されない)がある。この位置を一時的にでもある要素で埋められればハッシュテーブルの全ての要素を DELETEDにできる。直接この穴に配置される要素xは存在しないからハッシュ値を衝突させて insert()で玉突き処理を行わせなければいけない。完全ハッシュ関数を二つの要素のハッシュ値だけが衝突するように変更してみよう。玉突きで穴を一つ塞ぐことができるが、完全ハッシュ関数ではなくなることで穴は二つ(以上)になっていた。以下略。

拍子抜け。要素を重複して格納せず、DELETEDな要素を再利用している限り、ハッシュ表が DELETEDであふれることはない。あっけなさすぎて自作自演臭がしてきた。

蛇足も蛇足の別バージョン。全然かわりばえしない。

/* 要素xをハッシュ表hに追加 */
void insert(int x) {
  int i = hash(x);
  int d = -1; /* hash(x)に一番近い DELETEDの位置 */
  while (h[i] != EMPTY && h[i] != x) {
    if (d == -1 && h[i] == DELETED) {
      d = i;
      h[d] = x;
    }
    i = (i + 1) % B;
  }
  if (d == -1) {
    h[i] = x;
  } else if (h[i] != EMPTY) {
    h[i] = DELETED;
  }
}

0 ≦ hash(x) ＜ B は暗黙の前提にしてるけど、3つ目のミスだったりして。

コメントも読めばわかるけど、ミスが 1。修正過程で陥りやすい落とし穴が 2つくらい、なんだってば。(でもわかりにくい)