Michael J Swart recommends a unique index:
To avoid deadlocks when implementing the upsert pattern, make sure the index on the key column is unique. It’s not sufficient that all the values in that particular column happen to be unique. The index must be defined to be unique, otherwise concurrent queries can still produce deadlocks.
Read on for Michael’s thoughts as well as some smart commenters adding on.