What would be the best format for storing a relatively large amount of data (essentially a big hashmap) for quick retrieval using javascript? It would need to support Unicode as well.
XML, JSON?
Gigantic javascript objects are generally a sign that you're trying to do something you really shouldn't be doing. XML is even worse, it has to be parsed to form meaningful data.
In this case an AJAX query to RESTful interface to a proper database backend would probably serve you well.
Javascript object access (particularly for any query beyond accessing a single item by its hash) is very slow compared to even a basic database.