Generic NSMapTable replacement written in Swift
(Not a full review, but some remarks and suggestions.)

Generally, your code looks correct to me, I could not see obvious
errors or problems – for the single-threaded usage.

You cannot
assume that it will work correctly when used from multiple threads
simultaneously. 
Cocoa mutable collection types are not thread-safe (see Thread Safety Summary),
and – as far as I know – the same applies to Swift collections
(references: Swift: process Array in parallel using GCD, Swift mutable array thread safety, Swift Arrays are not Threadsafe).



In 

let watcher = DeallocWatcher { [weak self] in
    if let v = self?.dict[hashableBox] { self?.block(v) }
    self?.dict[hashableBox] = nil
}


self is (conditionally) unwrapped three times. I would use 
optional binding instead so that it is unwrapped only once.
You could also take advantage of the fact that removeValueForKey()
returns the old value (or nil):

let watcher = DeallocWatcher { [weak self] in
    if let s = self {
        if let v = s.dict.removeValueForKey(hashableBox) {
            s.block(v)
        }
    }
}




When a value for key is removed in

    else {
        objc_setAssociatedObject(key, unsafeAddressOf(self), nil, 0)
        dict[hashableBox] = nil // &lt;-- not needed!
    }


then the first line already causes the value to be removed from dict,
because disassociating the associated object fires the DeallocWatcher
callback. So the second line is not needed.



The keys and keyValues properties can be simplified using map():

public var keyValues: [(K, V)] {
    return map(dict) { (k, v) -&gt; (K, V) in (k.value!, v) }
}

public var keys: [K] {
    return Array(dict.keys.map { $0.value! })
}




You can also easily add conformance to additional protocols to make
your WeakKeyDictionary more look and feel like a real dictionary.

If you add the Printable protocol

public class WeakKeyDictionary&lt;K: AnyObject, V where K: Hashable&gt; : Printable {

    // ...
    public var description: String  {
        return "[ " + ", ".join(map(dict) { (k, v) in "\(k.value!) : \(v) " }) + "]"
    }
}


then println(wkdict) produces an output similar to a dictionary.

And with SequenceType 

public class WeakKeyDictionary&lt;K: AnyObject, V where K: Hashable&gt; : Printable, SequenceType {

    // ...
    public func generate() -&gt; GeneratorOf&lt;(K, V)&gt; {
        var gen = dict.generate()
        return GeneratorOf {
            if let (k, v) = gen.next() {
                return (k.value!, v)
            }
            return nil
        }
    }
}


you can enumerate keys and values like

for (k, v) in wkdict {
    println((k, v))
}