Solution to "First unique number" problem on Leetcode

lib.rs

use std::collections::{HashMap, HashSet, BTreeMap};
use std::hash::{Hasher, BuildHasherDefault};

struct FirstUnique {
    positions: HashMap<i32, usize, BuildHasherDefault<IdentityHasher>>,
    uniqs: BTreeMap<usize, i32>,
    new_idx: usize,
}

impl FirstUnique {
    fn new(nums: Vec<i32>) -> Self {
        use std::collections::hash_map::Entry;

        let mut non_uniqs = HashSet::with_capacity_and_hasher(
            nums.len() * 2,
            BuildHasherDefault::<IdentityHasher>::default(),
        );
        let mut positions = HashMap::with_capacity_and_hasher(
            nums.len() * 2,
            <_>::default(),
        );
        
        for (i, &n) in nums.iter().enumerate() {
            match positions.entry(n) {
                Entry::Vacant(e) => {
                    e.insert(i);
                }
                Entry::Occupied(e) => {
                    non_uniqs.insert(n);
                }
            }
        }
        
        let uniqs = positions.iter()
            .filter(|&(n, _)| !non_uniqs.contains(n))
            .map(|(&n, &i)| (i, n))
            .collect();
        
        Self {
            positions,
            uniqs,
            new_idx: nums.len(),
        }
    }
    
    fn show_first_unique(&self) -> i32 {
        self.uniqs.iter().next().map_or(-1, |(_idx, &n)| n)
    }
    
    fn add(&mut self, value: i32) {
        use std::collections::hash_map::Entry;

        match self.positions.entry(value) {
            Entry::Occupied(e) => {
                self.uniqs.remove(e.get());
            }
            Entry::Vacant(e) => {
                let idx = self.new_idx;
                e.insert(idx);
                self.uniqs.insert(idx, value);
                self.new_idx += 1;
            }
        }
    }
}

#[derive(Default)]
struct IdentityHasher(u64);

impl Hasher for IdentityHasher {
    fn write(&mut self, _: &[u8]) {
        unimplemented!()
    }
    
    fn write_i32(&mut self, value: i32) {
        self.0 = value as _;
    }
    
    fn finish(&self) -> u64 {
        self.0
    }
}