In most of the examples of refactoring there's a strong distinction made between changing how something works internally and changing its behavior.
The behavior is its external behavior, not internal. As a somewhat trivial example, in Common Lisp you may use an association list like:
'((a . b) (c . d) (e . f))
This is grossly inefficient for some operations, but functions as a map. You realize, "Oh, we have alists with, potentially, thousands of elements or have to search it over and over, it's killing our performance". So you replace that with a hash table to get that nice O(1) performance on a lot of your operations. Your users though, never see a behavioral change because they still access the data using the same methods as before:
(get-value map 'a)
To them, there has been no change, and consequently for behavioral tests there has also been no change. It performs better (so there is a change, obviously) but it does not impact the guarantees you offered users of the unit.
> This is grossly inefficient for some operations, but functions as a map
I believe it's actually faster than a hash table for a decently large n, around the order of 50. Obviously this is going to depend quite a lot on how clever your compiler is.
edit: I was off by an order of magnitude, 500 -> 50.
I'm not able to find if any of the free Common Lisps do any kind of CDR coding[1].
I've never benchmarked the two as I usually either need something small (so use alists) or of large or indeterminate size (so use hash tables). There's a clear performance difference between the two choices at that second case, but since I never hit the "middle ground" I don't know what the threshold is. It probably also varies with each implementation.
Hash tables, though, should be O(1) for retrieval and updates and amortized O(1) for insertions. Alists are O(n) for retrieval and updates and O(1) for insertions (if you don't check for the presence of the key).
If you want performance, you may be better off using arrays in some cases. Instead of an alist or a hash table, make a struct - or even just a cons cell like: (cons keys values). Then have your association function do a linear search for target key on (car table), e.g. via #'position, and use its index to fetch the value from (cdr table) directly.
The behavior is its external behavior, not internal. As a somewhat trivial example, in Common Lisp you may use an association list like:
This is grossly inefficient for some operations, but functions as a map. You realize, "Oh, we have alists with, potentially, thousands of elements or have to search it over and over, it's killing our performance". So you replace that with a hash table to get that nice O(1) performance on a lot of your operations. Your users though, never see a behavioral change because they still access the data using the same methods as before: To them, there has been no change, and consequently for behavioral tests there has also been no change. It performs better (so there is a change, obviously) but it does not impact the guarantees you offered users of the unit.