@H2CO3 I suppose it's possible to define our own "hashing" from n to an index on a Vector to avoid having to use HashMap. I suspect if you hash straight from n to index you'll end up with a kind of sparse Vector that's half missing at all times though. Anyway this is getting a bit side tracked since I was really just interested in figuring out why it's slower than Julia despite being mechanically almost identical (both using HashMap etc).
@gvissers I think you are doing Dijk's algorithm without memoization/caching. That's going to be an avoidable source of slow down since the recursion can actually hit the cache quite often (if you do cache). Just doing n = 100 would hit the cache 16 times, for example. I suspect the difference is on the order of O(logN^2) but that's just a hunch. It's true that at a smaller index (ie: n = 4784969) the caching might end up generating so much overhead it makes the code actually slower, however at higher n (ie: a billion) it's going to make a very big difference.