A combination of aatch and the PairHash improvements, minus the explicit size initialization of the sets.

neighbour_aatch_pair.rs

use std::collections::HashSet;
use std::hash::BuildHasherDefault;

use std::default::Default;
use std::hash::Hasher;

pub struct FnvHasher(u64);

impl Default for FnvHasher {
    #[inline]
    fn default() -> FnvHasher {
        FnvHasher(0xcbf29ce484222325)
    }
}

impl Hasher for FnvHasher {
    #[inline]
    fn finish(&self) -> u64 {
        self.0
    }

    #[inline]
    fn write(&mut self, bytes: &[u8]) {
        panic!("Don't use, only for pairs")
    }

    #[inline]
    fn write_i32(&mut self, value: i32) {
        self.0 <<= 10;
        self.0 ^= value as u64;
    }
}

type Set = HashSet<(i32, i32), BuildHasherDefault<FnvHasher>>;

fn new_set() -> Set {
	let fnv = BuildHasherDefault::<FnvHasher>::default();
	HashSet::with_hasher(fnv)
}

fn iterNeighbors<F>(mut f: F, (i, j): (i32, i32)) -> ()
    where F: FnMut((i32, i32)) -> ()
{
    f((i-1, j));
    f((i+1, j));
    f((i, j-1));
    f((i, j+1));
}

fn nthLoop(n: usize, mut s0: Set, s1: Set, mut s2: Set) -> Set {
    if n == 0 {
        return s1;
    } else {
        for &p in &s1 {
            let add = |p| {
                if !s2.contains(&p) && !s1.contains(&p) {
                    s0.insert(p);
                }
            };
            iterNeighbors(add, p);
        }
        s2.clear();
        return nthLoop(n-1, s2, s0, s1);
    }
}

fn nth(n: usize, p: (i32, i32)) -> Set {
    let mut s1 = new_set();
    let s2 = new_set();
    let mut s0 = new_set();

    s1.insert(p);
    nthLoop(n, s0, s1, s2)
}

fn main() {
    let s = nth(7000, (0, 0));
    println!("{}", s.len());
}