Упс, похоже я в первый раз таки неправильно понял задачу
Альтернатива - создание индекса.
все остальное - лишь вариации и комбинации на тему.

Но какой индекс можно создать для всех возможных регулярок? че за бред? или я что то не пони. В ЛЮБОМ СЛУЧАЕ. держишь ключи в виде строк в массиве.

потом делаешь фильтр по этому массиву и отбираешь только те под которые подойдет регулярка. что тут сложного и долгого?
это моментально делается, какой нахрен индекс! Плюс индекс тут не сделаешь даже при желании.

function regExpFilterKeys( object, regExpFilter ) {
	return Object.keys( object ).filter( function ( key ) {
		return regExpFilter.test( key )
	} )
}

А нужно ли делать именно для всех?
Вот автор уже вроде какой-то индекс себе составил, и приведенная им регулярка очень располагает к индексированию.
Кроме тех случаев, когда нужен только конкретный тип регулярки)
Например для автокомплита как раз нужно ориентироваться по ключам, и применят регулярку по первым символам
Не так уж моментально, ведь элементов у автора тысячи.
Но если такой перебор будет проводится только один раз в ответ на действие пользователя, то да, время будет более чем приемлимо

я уже сам не понимаю кто из вас неправильно меня понял :)

допустим есть такой хеш:
h={
'аня':[4,6,7,68],
'вова':[3,,53,55],
'вася':[,3,34,344],
'ваня':[34,34,34,],
'петя':[35,5,5,45]
}

я хочу сказать как-то так:

r = h[ /^в/ ];

и получить:

r={
'вова':[3,,53,55]
'вася':[,3,34,344]
'ваня':[34,34,34,]
}

но вообщем, я догадываюсь что это бывает только во сне :)

или с базой данных)

тебе функцию написать что ли О_О ?

function filterKeys ( object, regExp ) {

	var filteredKeys = Object.keys( object ).filter( function ( key ) {
		return regExp.test( key )
	} );

	var obj = {};

	for ( var i = 0; i < filteredKeys.length; i++ ) {
		var key = filteredKeys[i];
		obj[key] = object[key]
	}

	return obj
}

IE > 8

можно использовать обёртку, которая будет использовать бинарное дерево в качестве хранилища.

но легче решить эту задачу, просто убрав её :) нет трёхтысячного массива - нет проблемы :) (выборка нужных ключей с помощью БД, например)

хм...

вообщем, я решил не строить догадки, а посмотреть на реальное время необходимое для перебора 3300 записей...

в зависимости от регекспа и количества подходящих записей время оказалось < 4ms.

это замечательно.

а сподвигло меня на эксперимент то, что я пока не совсем понимаю ооп :)
и я решил проверить oo вариант Maxmaxmахimus'a:

var filteredKeys = Object.keys( object ).filter( function ( key ) {
		return regExp.test( key )
	} );

vs
просто:

var filteredKeys = [];
for ( var key in object ) { if ( regExp.test( key )  ) filteredKeys.push( key )}

время одинаково.

вообщем,
всем огромное спасибо :)

и, да, про бинарное дерево я пока не слышал, обязательно почитаю.

в ишаке 8 моих функций нет, но их можно эмулировать заплатками